Indexes are usually built by way of a data structure; typically, that structure takes the form of a “tree.” Most commonly, the structure of choice is a B-Tree, which is a hierarchical organization defined by the arrangement and interactions of its nodes.
High in a B-Tree’s hierarchy, you find a root node. Each of the items in that root node points to a collection of items in a child node. This can go on for multiple levels. Eventually, you reach the leaf nodes, where the data itself is stored. Those leaf nodes point back to the rows in the main table. To be technology specific, for instance, in MyISAM, those leaf nodes have offsets in the main data file – the main data file in a MyISAM table is just a sequential collection of rows.
The purpose of an index is to allow a user to very quickly traverse just such a structure – whatever form that structure or algorithm might take – and to locate and examine rows or ranges of …
[Read more]