B-Trees

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

• It is empty or has height > = 1
• Root has at least 2 children
• All non-terminal nodes have at least
  • m/2 children
  • m/2 - 1 values
• All terminal nodes are at the same level

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

• only read data nodes are in the leaf nodes
• use virtual keys
• provides a means for ordered data

Insertion into B-tree Example

Return to CIS 350 Index Page