Please enable JavaScript.

Coggle requires JavaScript to display documents.

B+ Tree Index - Coggle Diagram

- - - - redistribute entries evenly
      - push up middle key
- - - - 1 <= m <= 2d entries
    - - d <= m <= 2d entries (>= 50% occupancy)
      - m entries -> m + 1 pointers to lower-level nodes
        
        left: < k1
        
        right: >= km
    - - index entries exist only in leafs
      - index entries sorted according to search key
      - d <= m <= 2d entries (>= 50% occupancy)
      - m entries -> m pointers / rids + pointers to next and previous
    - - calculate from non-leaf
- - - - replace parent node with copied-up middle key
    - - delete an entry (key, pointer pair) from parent of L
      - may propagate up, and redistribute non-leafs