Index (information technology)

:"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

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 may be used as an 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 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.

For details on programming language support of the various features see Comparison of programming languages (array).

upport 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, for a successful lookup, examine half on average and all in a worst-case; O(N) or linear time. 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 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.

ee also

* Binary search algorithm Fast lookup for sorted lists sometimes known as the "binary chop" method
* Hash table Creating an index for using indexed 'lookup' where keys are not sequential