B-tree family

• B+ tree
• B-link tree (concurrent B+ tree)
• B epsilon tree (write-optimized B tree variant)
• Bw tree (lock free B+ tree)

Data structure

B+ tree is like B-tree but:

• true values are only stored in leaf nodes
• root node and inner nodes store “guarding” keys to help navigate down to leaf nodes
• sibling pointers are added for convenience