B-tree: an m-way search tree with these properties:

B - Tree: m - way search tree

  n:  # keys in  node {1 <= n < m}


type Triple = record K: keyType; A: pointer; S: pointer; end; Node = record n: integer; S0: subtree; tuple: array[1..2] of triple; end;

B-Tree order 3:

B* Tree must be 2/3 full

B+ Tree

Insertion into B-tree Example

Return to CIS 350 Index Page