Tables:   2-3-, 2-3-4- & B-Trees:   Introduction

Yet more tree structures for implementing lookup tables:

• 2-3-trees
  
  
• 2-3-4-trees
  
  
• B-trees
  
  

Height balanced, operations have O(log(n))-time complexity.

Binary search tree (and AVL tree) have

• one element, two sub-tree pointers, per `fork' node,
  
  
• therefore no spare room for more elements in forks,
  
  
• so new elements are inserted in new leaves.
  
  

2-3-trees have

• one or two elements per fork, up to three sub-tree pointers
  
  

• Ptr_1

  Elt_1

  Ptr_2

  Elt_2

  Ptr_3

  
  
• so a fork node may be full or only half full
  
  
• New elements can be added to internal fork nodes.
  
  

2-3-tree,   insert an element:

• First search (left/middle/right) to find the appropriate fringe node, then

• if space in the node, add index-element and (data-)pointer
  
  
• else node full:
  
  
  • i.e. would have 4 pointers (and 3 index-elements),   so must split the node:
    
    
  • divide pointers across old node and new node, and . . .
    
    
  • add pointer to new-node (and index-element) to parent . . .
    
    
  • which might split . . .
    
    
  • etc. (possibly up to root)

[lecturer: do insertion examples; class: take notes!]

2-3-tree:

• grows at the top when (if) root splits
  
  
• is always perfectly height balanced
  
  because [_____________________]
  
  
• element space from 50% to 100% occupied
  
  

2-3-4-tree:

• room for 3 elements and
  
  
• 4 pointers per fork node
  
  

• Ptr_1

  Elt_1

  Ptr_2

  Elt_2

  Ptr_3

  Elt_3

  Ptr_4

  
  
• Insertion can be as for 2-3-tree
  
  
• possibly splitting up to root, or . . .

2-3-4-tree

• . . . it is possible to keep splitting "local"
  
  
• by keeping some "spare room" low down the tree
  
  
• which means insert can be iterative (v. recursive).

This is done by:

• splitting any 4-nodes during descent
  
  
• which guarantees that every 4-node has a 2- or 3-node as parent

B-tree of order-k is the logical generalisation of 2-X-trees.

• All internal nodes (except perhaps the root) have between ceiling(k/2) and k sub-trees (and one fewer elements).
  
  
• All leaves are at the same depth
  
  
• height is O( log_k(n) )
  
  
• i.e. height decreases as k increases
  
  log₂ (1,000,000) = _________
  
  log₁₀ (1,000,000) = _________
  
  log₁₀₀ (1,000,000) = _________
  
  

The B-tree structure is popular for very large data sets

• especially stored on disc
  
  
• make order, `k', as large as possible
  
  (often to fit disc block size)
  
  
• want to reduce slowest operation
  
  
• i.e. reduce # of disc accesses
  
  

Tables:   2-3-, 2-3-4- & B-Trees:   Summary

• 2-3- and 2-3-4-trees are special case of B-tree
  
  
• possible to ensure only "local" changes on insert for 2-3-4- and higher order -trees.
  
  
• High order, k, good for B-tree on disc.

Prepare

• String searching algorithms