Btree

lastmod 2025-01-08created 2014-09-154 edits

• B-Tree: a multiway search tree. A tree-shaped data structure designed to search and update large files efficiently.
• B+Tree: similar to a B-Tree, but the actual data exists only at the lowest level and is linked sequentially. So it is much better for finding sequential values, but has the drawback of having to go all the way to the bottom level to find a specific value.
• B*Tree: reportedly a tree that uses redistribution to reduce the cost of merging in a B+Tree.

Libraries

• stx-btree: STX B+Tree C++ Template Classes.
• cpp-btree: C++ B-tree.

Favorite site

• Source code for a balanced tree (B-tree) ¹
• btree source (by. Thomas H. Cormen) v1.0 ²³
• B-trees and database indexes | GeekNews
  • [Original] B-trees and database indexes - Shows how a B-Tree works with an interactive GUI.
• B-Trees: a data structure that holds more than you'd expect | GeekNews
  • [Original] B-Trees: More Than I Thought I'd Want to Know | Ben Congdon
  • Recently, while reading Alex Petrov's Database Internals, came across material on how DBMS storage engines are implemented, especially on optimizing the B-Tree data structure
  • When learning B-Trees in college, understood them simply as a "better BST", so it never really clicked why they are actually used
  • The B-Tree structure is well suited to storing large-scale data and searching it quickly with disk I/O in mind
  • This post covers why B-Trees are needed, how they work, and what optimizations are possible in real implementations
  • Key features include packing many keys into a single node to reduce the number of disk accesses

References