Index (information technology)

This is referring to Index in the context of Information Technology. For other meanings, see Index.

Index has two distinct meanings in computer science: an integer which identifies an array element, and a data structure which enables sublinear-time lookup.

Array element identifier

When data objects are stored in an array, individual objects are selected by an index, a non-negative scalar integer.

Historically, a few programming languages have identified the first element in an array using an index value of 1, but it is common practice in modern languages to identify the first element with an index value of 0. It is also a common syntactic idiom in modern programming languages to use square brackets to contain index values. If the variable sheep identifies an array, in FORTRAN the first sheep would be identified as sheep(1), while many modern computer languages would use sheep[0].

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.