Index (information technology)
From Wikipedia, the free encyclopedia
- This is referring to Index in the context of Information Technology. For other meanings, see Index.
In computer science, an index can be:
- an integer which identifies an array element
- a pointer data element.
- a data structure that enables sublinear-time lookup
[edit] Array element identifier
When data objects are stored in an array, individual objects are selected by an index which is usually a non-negative scalar integer. Indices are also called subscripts.
There are three ways in which the elements of an array can be indexed:
- 0 (zero-based indexing)
- The first element of the array is indexed by subscript of 0
- 1 (one-based indexing)
- The first element of the array is indexed by subscript of 1.
- n (n-based indexing)
- The base index of an array can be freely chosen. Usually programming languages allowing n-based indexing also allow negative index values and other scalar data types like Enumerations, or Characters to be uses as array index.
Arrays can have multiple dimensions, thus it is not uncommon to access an array using multiple indices. For example a two dimensional array A with 3 rows and 4 columns might provide access to the element at the 2nd row and 4th column by the expression: A[1,3] (in a row major language) and A[3,1] (in a column major language). Thus two indices are used for a two dimensional array, 3 for a 3 dimensional array, and n for an n dimensional array.
For details on programming language support of the various features see Comparison of programming languages (array).
[edit] Support for fast lookup
Suppose a data store contains N data objects. A naive algorithm for looking up some particular object will consider each object and will thus, on average, have to examine half (for a successful lookup) or all of them; O(N) or linear time in computer-science terms. Since data stores commonly contain large numbers of objects and since lookup is a common operation, it is often desirable to improve this performance.
An index is any data structure which improves the performance of lookup. There are many different data structures used for this purpose, and in fact a substantial proportion of Computer Science is devoted to the design and analysis of index data structures. There are complex design trade-offs involving lookup performance, index size, and index update performance. Many index designs exhibit logarithmic (O(log(N)) lookup performance and in some applications it is possible to achieve flat (O(1)) performance.
All database software includes indexing technology in the interests of improving performance. See Index (database).
One specific and very common application is in the domain of information retrieval, where the application of a full-text index enables rapid identification of documents based on their textual content.
