The evolution of effective B-tree
- 1 September 2001
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMOD Record
- Vol. 30 (3) , 64-69
- https://doi.org/10.1145/603867.603878
Abstract
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.Keywords
This publication has 10 references indexed in Scilit:
- Order preserving string compressionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Improving index performance through prefetchingPublished by Association for Computing Machinery (ACM) ,2001
- Making B+- trees cache conscious in main memoryPublished by Association for Computing Machinery (ACM) ,2000
- B-tree page size when caching is consideredACM SIGMOD Record, 1998
- The five-minute rule ten years later, and other computer storage rules of thumbACM SIGMOD Record, 1997
- AlphaSortPublished by Association for Computing Machinery (ACM) ,1994
- Multi-table search for B-tree filesPublished by Association for Computing Machinery (ACM) ,1979
- An encoding method for multifield sorting and indexingCommunications of the ACM, 1977
- Prefix B -treesACM Transactions on Database Systems, 1977
- Organization and maintenance of large ordered indexesActa Informatica, 1972