Memory based B+ tree in C++

Definition of the B-tree

Let h >= 0 be an integer, and k a natural number. A directed tree T is in the class (k, h) of B-trees if T is either empty (i.e. h=0) or has the following properties:

• Each path from the root to any leaf has the same length h, also called the height of T, i.e. h is eequal to the number of nodes in path.

• Each node except the root and the leaves has at least (k + 1) sons. The root is a leaf or has at least two sons.

• Each node has at most (2k + 1) sons.

Properties of the B-tree

• Each page holds between k and 2k keys (index elements) except the root page which may hold between 1 and 2k keys.

• Let the number of keys on a page P, which is not a leaf, be L. Then P has L+1 sons.

• Within each page P the keys are sequential in increasing order: x₁, x₂, ... x_L, where k <= L <= 2k except for the root page for which 1 <= L <= 2k.

• Furthermore, P contains (L + 1) pointers P₀, P₁ ... P_L to the sons of P. On leaf pages these pointers are undefined (i.e. null pointers).

• Let P(p_i) be the page to which P_i points, let K(P_i) be the set of keys on the pages of that maximal subtree of which P(P_i) is the root. Then for the B-trees considered here the following conditions shall always hold:

  1. for each y in K(p₀) y < x_i
  2. for each y in K(p_i) x_i < y < x_i+1 for i = 1,2,...,L-1
  3. for each y in K(p_L) x_L < y

References, books

• A. Silberschatz, H.F. Korth, S. Sudarshan, "Database System Concepts", 6th ed. (McGraw Hill, 2011)

• R. Ramakrishnan, J. Gehrke, "Database Management Systems ", 3rd ed. (McGraw Hill, 2003)

• A. Drozdek, D.L. Simon "Data Structures in C", (PWS, 1995)

References, articles

• R. Bayer E.M. McCreight, "Organization and maintenance of large ordered indexes", Acta Informatica, Volume 1, Issue 3, pp. 173–189, Year 1972, PDF

• R. Bayer, "Symmetric binary B-Trees: Data structure and maintenance algorithms", Acta Informatica, Volume 1, Issue 4, pp. 290–306, Year 1972, Abstract

• R. Bayer, K. Unterauer, "Prefix B-trees", ACM Transactions on Database Systems, Volume 2, Issue 1, pp. 11-26, Year 1977, Abstract

• D. Comer, "Ubiquitous B-Tree", ACM Computing Surveys, Volume 11, Issue 2, Pages 121-137, Year 1979, PDF

• J. Zhou "A B+-tree Index fot the Know-It-All Database Framework", 2003, PDF

• D. Lomet, "The Evolution of Effective B-tree: Page Organization and Techniques: A Personal Account", SIGMOD Record, Volume 30, No. 3, 2001, PDF

• R. ORLANDIC, H.M. MAHMOUD "STORAGE OVERHEAD OF O-TREES, B-TREES AND PREFIX B-TREES: A COMPARATIVE ANALYSIS", International Journal of Foundations of Computer Science, PDF

• G. Graefe, "Write-Optimized B-Trees ", Proceedings of the 30th VLDB Conference, 2004, PDF

• G. Graefe, "A Survey of B-Tree Logging and Recovery Technique", ACM Transactions on Database Systems, Vol. 35, No. 3, Article 16, 2012, PDF

• G. Graefe, "Modern B-Tree Techniques", Foundations and Trends in Databases, Vol. 3, No. 4, pp. 203–402, Year 2010, PDF

• G. Graefe, "A Survey of B-Tree Locking Technique", ACM Transactions on Database Systems, Vol. 35, No. 3, Article 16, Year 2010, PDF

• P. Wang, "An In-Depth Analysis of Concurrent B-tree Algorithms", Massachusetts Institute of Technology Report MIT/LCS/TR-496, Year 1991, PDF

• Y.-S. KWONG,D. WOOD, "A New Method for Concurrency in B-Trees", IEEE TRANSACTIONS ON SOFTWARE ENGINEERING, VOL. SE-8, NO. 3, pp. 211-222, Year 1982, PDF

• M.K. Aguilera, W. Golab, M.A. Shah, "A Practical Scalable Distributed B-Tree", VLDB, Year 2008, PDF

Similar projects in C++:

• cpp-btree

• STX

• From Wikipedia: B+Tree (Caution! The code has the bug in deletion procedure!)

Author

• Zbigniew Romanowski
• e-mail: romz@wp.pl