Screen Shot 2021-11-10 at 11.31.17 AM.png

Screen Shot 2021-11-10 at 11.36.03 AM.png

Screen Shot 2021-11-10 at 11.36.45 AM.png

Space Usage Gurantee

Search on B+Tree

Screen Shot 2021-11-10 at 11.40.42 AM.png

B+Tree Insertion

  1. No overflow

  2. Leaf overflow

    Screen Shot 2021-11-15 at 10.17.35 AM.png

    smaller than 70, go left to 50

    larger than 50, go right to 50

    No space! Overflow

    Allocate a new node and move half of the entries in the overflowing node to the new node

    Screen Shot 2021-11-15 at 10.19.41 AM.png

    Copy the first key of the new node to parent (insert the value and the pointer to the node to the parent)

    Screen Shot 2021-11-15 at 10.21.32 AM.png

  3. non-leaf overflow

    Screen Shot 2021-11-15 at 10.26.49 AM.png

    Now we need to add a new pointer to the parent, but we don't have space on the parent node

    Screen Shot 2021-11-15 at 10.27.08 AM.png

    Now we need to split the parent node to add more space

    Screen Shot 2021-11-15 at 10.29.15 AM.png

    We need to push and move the middle key to its parent

    Screen Shot 2021-11-15 at 10.29.46 AM.png

    Screen Shot 2021-11-15 at 10.30.22 AM.png

  4. New root

    Screen Shot 2021-11-15 at 10.32.08 AM.png

    Screen Shot 2021-11-15 at 10.32.54 AM.png

    Screen Shot 2021-11-15 at 10.33.48 AM.png

Screen Shot 2021-11-15 at 10.33.58 AM.png

B+ Tree Insertion