B Trees

Tree that store multiple elements in a single node

Properties

• Each node is a block containing multiple “keys”
  • The maximum number of keys per node is L
• n-aray trees (each node has up to n children)
  • Called “Order n tree”
• Follows the BST property of less on the right and greater on the left
  • All keys are in sorted order
• Built bottom up (opposite of other trees)
  • Once we hit the capacity of a leaf, you split the node
• Leafs are at the same depth
• Keys
  • All keys are in sorted order
  • Non leaf nodes store up to $n-1$ keys (L is at-most n-1 for internal nodes)
    • Because $k$ keys → $k+1$ children
  • All keys are in sorted order
• Children
  • Root is a leaf or has $2^n$ children
  • Non-leaf nodes have $\lceil n/2{\rceil }^n$ children
  • Maximum children is at most $n$ for all nodes

Special Cases

• Perfect BST: (n=2, L=1)
• 2-3-4 or 2-4: (n=4, L=3)
• 2-3: (n=3, L=2)

Insertion

1. Insert element where it belongs in the tree
2. If node has more than the amount of allowed amount of keys, burst the node and move the middle node up a level
3. Repeat the bursting process on the node above recursively

B+ Tree

• B trees plus some extra things
• All data is stored in the leaves
  • Higher leaves are only used to find the data at the bottom
  • Means there can be duplicates of data at he bottom higher up
• Leaves have pointers to the other leaves forming a linked list for faster traversal
  • it’s almost like a linked list with faster random access overall
• Benefits
  • Faster Access
  • Faster Deletion
• Drawbacks
  • More memory due to duplicate nodes
• Note: when asked how many unique keys are in a tree only count the keys in the leaves if the tree is B+

Application

• Caches
• Indexing File systems
• Indexing databases
• Finding memory across the memory hierarchy

Performance

• Height: Between ${\log }_{L+1}n$ and ${\log }_{2}n$
• Largest possible height is when all leaf nodes have $L/2$ items
• Smallest possible height is when all nodes have $L$ items
• Overall height is $O(\log n)$
• Search time: $O(Lh)\sim O(L\log n)$
  • h = height of tree
  • n = maximum names of children