B-Tree Indexes

Derik Hammer is starting a new series on index types and has started with the venerable B-tree:

On more than one occasion I have been told that the B-Tree index is the index structure which was designed after the A-Tree index. Another common misconception is that it stands for Binary-Tree. As logical as those may seem, they are false. The ‘B’ in B-Tree does not actually have any specific meaning. Check out Ed McCreight’s explanation here (16:08) where he admits that the name discussion was never settled.

In its most basic form, the B-Tree index is a hierarchy of data pages (page structures lightly touched on in the next post of this series). The lowest level is called the leaf level, the highest level is the index root, and all levels in between are the intermediate levels. This structure is an improvement over the Binary Tree index because its balanced nature greatly improved the performance of maintenance operations such as, INSERT, DELETE, and UPDATE.

On the terminological point, I’d always heard that the “B” stood for “Balanced” because of the level flatness—in contrast to a “normal” tree, you wouldn’t have more than a pre-defined number of levels separation (usually one) between leaf nodes.

Related Posts

Troubleshooting Memory-Optimized Index Performance

Kunal Karoth has a post up on performance troubleshooting with In-Memory OLTP: In the previous blog post In-Memory OLTP Indexes – Part 1: Recommendations, we gave you an update on the latest features of In-Memory OLTP technology. We also summarized the key characteristics of memory-optimized indexes and shared some guidelines and recommendations on how to best […]

Read More

Indexing Tradeoffs

Jeff Schwartz continues his series on index tuning, including a section on what happens when you have too many indexes on a table: Larger numbers of indices create exponentially more query plan possibilities. When too many choices exist, the Optimizer will give up partway through and just pick the best plan thus far. As more […]

Read More

Categories

April 2016
MTWTFSS
« Mar May »
 123
45678910
11121314151617
18192021222324
252627282930