Please help improve this article or section by expanding it. Further information might be found on the talk page or at requests for expansion. (May 2007)

A database index is a data structure that improves the speed of operations in a table. Indexes can be created using one or more columns, providing the basis for both rapid random lookups and efficient ordering of access to records. The disk space required to store the index is typically less than the storage of the table (since indexes usually contain only the key-fields according to which the table is to be arranged, and excludes all the other details in the table), yielding the possibility to store indexes into memory from tables that would not fit into it. In a relational database an index is a copy of part of a table. Some databases extend the power of indexing by allowing indexes to be created on functions or expressions. For example, an index could be created on upper(last_name), which would only store the uppercase versions of the last_name field in the index. Another option sometimes supported is the use of "filtered" indexes, where index entries are created only for those records that satisfy some conditional expression. A further aspect of flexibility is to permit indexing on user-defined functions, as well as expressions formed from an assortment of built-in functions. All of these indexing refinements are supported in Visual FoxPro, for example.^[1] Image File history File links This is a lossless scalable vector image. ... This article is about computing. ... A binary tree, a simple type of branching linked data structure. ... In relational databases, SQL databases, and flat file databases, a table is a set of data elements (values) that is organized using a model of horizontal rows and vertical columns. ... In the context of a relational database, a column of a table is a set of data values of a particular simple type, one for each row of the table. ... A relational database is a database that conforms to the relational model, and refers to a databases data and schema (the databases structure of how that data is arranged). ... An expression in a programming language is a combination of values and functions or procedures, interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then returns another value. ... A User-Defined Function, or UDF, is a function provided by the user of a program or environment, in a context where the usual assumption is that functions are built into the program or environment. ... Visual FoxPro is a data-centric object-oriented and procedural programming language produced by Microsoft. ...

Indexes may be defined as unique or non-unique. A unique index acts as a constraint on the table by preventing identical rows in the index and thus, the original columns.

Architecture

Index architectures can be classified as clustered or non-clustered. A non-clustered index normally contains a reference to a block that contains the row data for which the particular index item has been constructed. This block will hold several other rows depending on the row size. For each index lookup on a non-clustered index a data block that houses the row sought after must also be retrieved.

Clustering re-orders the data block in the same order as the index, hence it is also an operation on the data storage blocks as well as on the index. Exact operation of database systems vary, but because the row data can only be stored in one order physically only one clustered index may be created on a given database table. Clustered indexes can greatly increase access speed, but usually only where the data is accessed sequentially in the same or reverse order of the clustered index, or when a range of items are selected.

Since the physical records are in this sort order on disk the next row item in the sequence is immediately before or after the last one, and so fewer data block reads are required. The primary feature of a clustered index is therefore the ordering of the physical data rows in accordance with the index blocks that point to them. Some databases separate the data and index blocks into separate files, while others intermix the two different types of data blocks within the same physical file(s). Databases that use the latter scheme may be said to store the actual data in the leaf node of the index, whereas, in fact there is still a distinction between the index and the data block, and the data blocks can be traversed without using the index by way of a link list that links the data blocks in order.

In Microsoft SQL Server, the leaf node of the clustered index corresponds to the actual data, not simply a pointer to data that resides elsewhere, as is the case with a non-clustered index. ^[2] Each relation can have a single clustered index and many unclustered indexes. ^[3]. Microsoft SQL Server is a relational database management system (RDBMS) produced by Microsoft. ... 9, 14, 19, 67 and 76 are leaf nodes. ...

Indexes can be implemented using a variety of data structures. Popular indices include balanced trees, B+ trees and hashes.^[4] In computing, a self-balancing binary search tree is a binary search tree that attempts to keep its height, or the number of level of nodes beneath the root, as small as possible at all times, automatically. ... -1... In computer science, a hash table is a data structure that speeds up searching for information by a particular aspect of that information, called a key. ...

Column order

The order in which columns are listed in the index definition is important. It is possible to retrieve a set of row identifiers using only the first indexed column. However, it is not possible or efficient (on most databases) to retrieve the set of row identifiers using only the second or greater indexed column.

For example, imagine a phone book that is organized by city first, then by last name, and then by first name. If given the city, you can easily extract the list of all phone numbers for that city. However, in this phone book it would be very tedious to find all the phone numbers for a given last name. You would have to look within each city's section for the entries with that last name. Some databases can do this, others just won’t use the index..

Applications and limitations

Indexes are useful for many applications but come with some limitations. Consider the following SQL statement: SELECT first_name FROM people WHERE last_name = 'Finkelstein';. To process this statement without an index the database software must look at the last_name column on every row in the table (this is known as a full table scan). With an index the database simply follows the b-tree data structure until the Finkelstein entry has been found; this is much less computationally expensive than a full table scan. SQL (IPA: or ), commonly expanded as Structured Query Language, is a computer language designed for the retrieval and management of data in relational database management systems, database schema creation and modification, and database object access control management. ... B-trees are tree data structures that are most commonly found in databases and filesystem implementations. ...

Consider this SQL statement: SELECT email_address FROM customers WHERE email_address LIKE '%@yahoo.com';. This query would yield an email address for every customer whose email address ends with "@yahoo.com", but even if the email_address column has been indexed the database still must perform a full table scan. This is because the index is built with the assumption that words go from left to right. With a wildcard at the beginning of the search-term the database software is unable to use the underlying b-tree data structure. This problem can be solved through the addition of another index created on reverse(email_address) and a SQL query like this: SELECT email_address FROM customers WHERE reverse(email_address) LIKE reverse('%@yahoo.com');. This puts the wild-card at the right most part of the query (now moc.oohay@%) which the index on reverse(email_address) can satisfy. The term wildcard character has the following meanings: // In telecommunications, a wildcard character is a character that may be substituted for any of a defined subset of all possible characters. ...

Types

Bitmap index

Main article: Bitmap index

A bitmap index is a special kind of index that stores the bulk of its data as bitmaps and answers most queries by performing bitwise logical operations on these bitmaps. The most commonly used index, such as B+trees, are most effective if the values it indexes do not repeat or repeat a relatively smaller number of times. In contrast, the bitmap index is designed for cases where the values of a variable repeats very frequently. For example, the gender field in a customer database usually contains two distinct values, male or female. For such variables, the bitmap index can have a significant performance advantage over the commonly used trees. A bitmapped index is a special kind of index that is particularly useful in data warehousing for columns that have a low number of distinct values (low cardinality). ...

Dense index

A dense index in databases is a file with pairs of keys and pointers for every record in the data file. Every key in this file is associated with a particular pointer to a record in the sorted data file. In clustered indexes with duplicate keys the dense index points to the first record with that key.^[5] This article is about computing. ... A computer file is a collection of information that is stored in a computer system and can be identified by its full path name. ... In computer science, a pointer is a programming language data type whose value refers directly to (or “points to”) another value stored elsewhere in the computer memory using its address. ... This article is about the data structure. ...

Sparse index

A sparse index in databases is a file with pairs of keys and pointers for every record in the data file. Every key in this file is associated with a particular pointer to the block in the sorted data file. In clustered indexes with duplicate keys the sparse index points to the lowest search key in each block.

See also

• Create database index in Oracle, MySQL and SQL server
• How to measure Index Selectivity

Please add coverage of Hashing in Link Lists

References