Exercises for B+ Trees

Compare and Contrast B+ trees and BSTs

For the following questions, be sure to also think about whether the answer varies based on the type of node; mainly, root node, internal node, and leaf node


1. There are several types of balanced BSTs, such as AVL Tree. What is different about a B+ trees guarantee of balance and an AVL Tree's guarantee?
   
   
2. How many keys in a BST node? How many keys in a B+ tree node? Does this vary based on the type of node?
   
   
3. How many pointers in a BST node? B+ tree node?
   
   
4. How many keys per node? Values per node?
   
   
5. Given a BST height of h >= 1, what are the minimum number of nodes searched if the key exists? If the key doesn't exist? Provide the maximum for each as well
   
   
6. Answer the previous question for a a B+ tree
   
   
7. What is the central trade-off with B+ trees. That is, what are we gaining relative to BSTs? What is the cost? (Read the next question if you are not sure)
   
   
8. If all data resides in memory, why are BSTs a better choice for a data structure? Why does this not hold true in typical DBs where data resides mainly on disk?
   
   

   Page formatting

9. A good value of d is one that maximizes the usage of an internal node page. Assume integer keys and a page size variable SIZE and that each page needs to store it's level number as well. Calculate the value order of a B+ tree that maximizes page usage.
   
   
10. For the previous answer, what range of number of keys do we expect for a node?
    
    
11. How much data can we store on each leaf page? Is it the same as an internal node? Why or why not?
    
    
12. What is storing variable-length attributes problematic? What strategies do we have to counter these problems?