2.17 B Tree

1. What Is a B Tree

• One kind of self-balancing search tree
• A multiway search tree
  • 

2. Why B Tree Is Needed

2.1. Background

• Database query requirements:
  • Find data by a value, such as select * from user where id=1234；
  • Find data by a range, such as select * from user where id > 1234 and id < 2345
• When the amount of data is large, it has to be stored on disk, so disk I/O is involved.
  • According to total disk I/O time = number of disk I/Os * time per I/O, since the time of each I/O is fixed, total disk I/O time depends on the number of disk I/Os
• Spatial locality: if some data is accessed, nearby data is likely to be accessed soon.
  • According to spatial locality, when disk reads a piece of data, it does not read only one record at a time, but reads many records, more precisely several blocks (each block is 512 Bytes), that is, one page (generally 4 k, 8 k, or 16 k)

2.2. HashMap

• Advantage: average efficiency of looking up a value in HashMap is O(1)
• Problem: range lookup is O(N), because keys are not sorted

2.3. Sorted Array

• Advantage: binary search is O(logN)
• Problem: inserting a record in the middle requires moving all records after it, which is expensive; an array also requires contiguous storage

2.4. Sorted Linked List

• Advantage: contiguous storage is not required; insertion and deletion do not require moving other elements
• Disadvantage: even when sorted, lookup is still O(N)

2.5. Skip List

• Advantage: expected complexity of insert/delete/search/update is O(logN)
• Disadvantage: the height can be large, causing many I/Os when the data set is large

2.6. Balanced Binary Trees (Red-Black Tree, AVL Tree)

• Advantage: lookup by value is O(logN); range lookup can use in-order traversal with O(N)
• Problem:
  • Each binary-tree node can store only one key. With large data sets the tree becomes very tall, and tree height corresponds roughly to the number of disk I/Os, so a taller tree means longer total disk I/O time
  • Why does tree height correspond to disk I/O count?
    • Tree nodes are connected by pointers rather than stored as one contiguous memory region, so we can assume each I/O reads one node; disk I/O count is therefore roughly equal to binary-tree height

2.7. B Tree

• A B Tree stores more keys in one node, so compared with a binary tree it is wider and shorter. This reduces the number of disk accesses
• How many keys should each node store? Since the operating system loads data in page-sized units, each node can be designed to be about the same size as a page

2.8. B+Tree

• Non-leaf nodes store only keys, not values. Therefore one I/O can load more keys for filtering
• Leaf nodes are linked with a doubly linked list. Therefore range queries are faster

3. Balanced Binary Tree vs B Tree

• The biggest difference between B-family trees and binary search trees is that each node can have multiple children rather than only two
  • Balanced binary tree
    • 
  • B Tree
    • 
• Suppose we read the node containing 20. A binary search tree can read only that node and nearby unrelated data, while a B Tree can read a group of related values such as 20…50…70

4. B+Tree vs B Tree

• B-Tree
  • 
• B+Tree
  • 
• As shown, the main differences between B-Tree and B+Tree are:

1. Non-leaf nodes of the former store data in addition to lookup keys; the latter stores only keys
   • This allows a B+Tree to read more keys for lookup in one I/O
2. Leaf nodes of the former do not duplicate keys, while the latter duplicates them and links them in order
   • This makes B+Tree more suitable for range lookup

5. References

• Introduction of B-Tree - GeeksforGeeks
• A Detailed Explanation: What Is a B-Tree? - Zhihu
• B/B+ Trees from MongoDB and MySQL - CSDN