In computer science, an index can be:
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:
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).
Suppose a data store contains N data objects. A straightforward approach is to use the index number of an object as its identifier, that is, a company might request that its customers always mention their account number and that number directly identifies the customer's record though in practice the account number should have additional digits to support a check against mistype. This is the usage of the first form, an integer that identifies an array element.
But using such numbers may not be convenient, just as "wikipedia.org" is preferred to the thirty-two bit number represented by 208.80.152.2, which is 3,494,942,722. A naive algorithm would be to prepare a list of such names and to find some particular name, each would be tested in succession from first to last. For a successful lookup this will examine half on average and all in a worst-case as with "not found"; O(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 which 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.
stock | retire | vm
Why are we here?
All text is available under the terms of the GNU Free Documentation License
This page is cache of Wikipedia. History