The Evolution of Effective B-tree Page Organization and Techniqu...

The Evolution of Effective B-tree Page Organization and Techniques: A Personal AccountDavid Lomet Microsoft ResearchRedmond, WA 98052 lomet@microsoft.com1. IntroductionAn under-appreciated facet of index search structures is the importance of high performance search within B-tree internal nodes. Much attention has been focused on improving node fanout, and hence minimizing the tree height [BU77, LL86]. [GG97, Lo98] have discussed the importance of B-tree page size. A recent article [GL2001] disc