If you're using MySQL, you likely have indexes that are powered by B-trees. The B-tree is a powerful data structure, and is frequently used to construct indexes in relational databases. If you are using the InnoDB storage engine, it is the only choice for your index, save for spatial indexes. However, MySQL has a secret weapon for making lookups with these types of indexes even faster: the Adaptive Hash Index, or AHI. Before jumping into how this works, let's take a few moments to review B-trees, the InnoDB buffer pool, and how these work together during index lookups.
The B-tree data structure has been used by computer systems for decades. It is particularly useful in the context of file system and data storage applications, due to the fact that each node can store many values. This is useful in …
[Read more]