B-Tree invariants

We mentioned in chapter 11.1 that order matters when inserting into a BST.

Question: Is this also true for a B-Tree?

Exercise 11.3.1: Insert 1-7 into a B-tree in that order. What is the height of the tree? Can we change the order of the insertions so that we can decrease the height? Here is a [cool B-tree visualizer](https://www.cs.usfca.edu/~galles/visualization/BTree.html\) that might help!

Solution: Yes, we can get a tree of height 1 by inserting in this order: 2, 3, 4, 5, 6, 1, 7.

Yes, depending on the order you insert nodes the height of a B-tree may change. However, the tree will always be bushy.

A B-tree has the following helpful invariants:

  • All leaves must be the same distance from the source.

  • A non-leaf node with kk items must have exactly k+1k+1 children.

In tandem, these invariants cause the tree to always be bushy.

B-Tree runtime analysis

The worst-case runtime situation for search in a B-tree would be if each node had the maximum number of elements in it and we had to traverse all the way to the bottom. We will use LL to denote the number of elements in each node. This means would would need to explore logN\log N nodes (since the max height is logN\log N due to the bushiness invariant) and at each node we would need to explore LL elements. In total, we would need to run LlogNL \log N operations. However, we know LL is a constant, so our total runtime is O(logN)O(\log N).

B-Tree deletion (Extra)

See these extra slides if you're curious. We won't discuss them here.

Summary

BSTs have best case height Θ(logN)\Theta (\log N), and worst case height Θ(N)\Theta (N).

  • Big O is not the same thing as worst case!

B-Trees are a modification of the binary search tree that avoids Θ(N)\Theta (N) worst case.

  • Nodes may contain between 11 and LL items.
  • contains works almost exactly like a normal BST.
  • add works by adding items to existing leaf nodes.
    • If nodes are too full, they split.
  • Resulting tree has perfect balance. Runtime for operations is O(logN)O(\log N).
  • Have not discussed deletion. See extra slides if you’re curious.
  • Have not discussed how splitting works if L>3L > 3 (see some other class).
  • B-trees are more complex, but they can efficiently handle ANY insertion order.

results matching ""

    No results matching ""