In computer science, an index can be:
Contents |
When data objects are stored in an array, individual objects are selected by an index that is usually a non-negative scalar integer. Indices are also called subscripts. An index maps the array value to a stored object.
There are three ways in which the elements of an array can be indexed:
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 three rows and four 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) in the case of a zero-based indexing system. Thus two indices are used for a two dimensional array, three for a three dimensional array, and n for an n dimensional array.
Suppose a data store contains N data objects, and it is desired to retrieve one of them based on the value of one of the object's fields. A naive implementation would retrieve and examine each object until a match was found. A successful lookup would retrieve half the objects on average; an unsuccessful lookup all of them for each attempt. This means that the number of operations in the worst case is Ω(N) or linear time. Since data stores commonly contain millions of objects and since lookup is a common operation, it is often desirable to improve on this performance.
An index is any data structure that improves the performance of lookup. There are many different data structures used for this purpose, and in fact a substantial proportion of the field 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.