B-tree insertion

 function NewNode( k1 : typekey; p0, p1 : btree ) : btree; var t : btree; begin new( t ); t^.p[0] := p0; t^.p[1] := p1; t^.k[1] := k1; t^.d := 1; NewNode := t end; procedure insert( key : typekey; var t : btree ); var ins : typekey; NewTree : btree; function InternalInsert( t : btree ) : typekey; var i, j : integer; ins : typekey; tempr : btree; begin if t=nil then begin {*** The bottom of the tree has been reached: indicate insertion to be done ***} InternalInsert := key; NewTree := nil end else with t^ do begin InternalInsert := NoKey; i := 1; while ( ik[i] ) do i := i+1; if key = k[i] then Error {*** Key already in table ***} else begin if key > k[i] then i := i+1; ins := InternalInsert( p[i-1] ); if ins <> NoKey then {*** the key in "ins" has to be inserted in present node ***} if d<2*M then InsInNode( t, ins, NewTree ) else {*** Present node has to be split ***} begin {*** Create new node ***} if i<=M+1 then begin tempr := NewNode( k[2*M], nil, p[2*M] ); d := d-1; InsInNode( t, ins, NewTree ) end else tempr := NewNode( ins, nil, NewTree ); {*** move keys and pointers ***} for j:=M+2 to 2*M do InsInNode( tempr, k[j], p[j] ); d := M; tempr^.p[0] := p[M+1]; InternalInsert := k[M+1]; NewTree := tempr end end end end; begin ins := InternalInsert( t ); {*** check for growth at the root ***} if ins <> NoKey then t := NewNode( ins, t, NewTree) end;