Key points are not available for this paper at this time.
An 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 discusses internal node architecture, but the subject is buried in a single section of the paper.In this short note, I want to describe the long evolution of good internal node architecture and techniques, including an understanding of what problem was being solved during each of the incremental steps that have led to much improved node organizations.
David Lomet (Sat,) studied this question.