Slow Indexes
This week I was exposed to an awesome website (Use the Index, Luke!) that helped me understand how databases work. One of key feature of databases is indexes. Indexes in a database are just like indexes at the back of a book: They point to the place you need to go. Databases use something called a B+ tree to implement indexes. A B+ tree is a combination of a balanced tree with a linked list. While the traversal time from the root of the tree to the leaves is logarithmic, the traversal time from leaf-to-leaf is linear. If a select statement requests a range of rows, for example, the index will allow the database to quickly find the start of the range, but it will still have travel to the end of the range one leaf at a time. There is also the time needed to actually fetch the data from the table.
To summarize, there are actually three steps to an index lookup: tree traversal, leaf node following, and data fetching. The only step that is guaranteed to be quick is the first one (tree traversal). The other 2 can take a long time if there are many records to go through and retrieve. Therefore, it is a myth that "slow indexes" actually exist, and taking drastic action (such as rebuilding the index) is not necessary.
No comments:
Post a Comment