Java Reference
In-Depth Information
privateTTNode<Key,E>inserthelp(TTNode<Key,E>rt,
Keyk,Ee){
TTNode<Key,E>retval;
if(rt==null)//Emptytree:createaleafnodeforroot
returnnewTTNode<Key,E>(k,e,null,null,
null,null,null);
if(rt.isLeaf())//Atleafnode:inserthere
returnrt.add(newTTNode<Key,E>(k,e,null,null,
null,null,null));
//Addtointernalnode
if(k.compareTo(rt.lkey())<0){//Insertleft
retval=inserthelp(rt.lchild(),k,e);
if(retval==rt.lchild())returnrt;
elsereturnrt.add(retval);
}
elseif((rt.rkey()==null)||
(k.compareTo(rt.rkey())<0)){
retval=inserthelp(rt.cchild(),k,e);
if(retval==rt.cchild())returnrt;
elsereturnrt.add(retval);
}
else{//Insertright
retval=inserthelp(rt.rchild(),k,e);
if(retval==rt.rchild())returnrt;
elsereturnrt.add(retval);
}
}
Figure10.15 The 2-3 tree insert routine.
10.5
B-Trees
This section presents the B-tree. B-trees are usually attributed to R. Bayer and
E. McCreight who described the B-tree in a 1972 paper. By 1979, B-trees had re-
placed virtually all large-file access methods other than hashing. B-trees, or some
variant of B-trees, are the standard file organization for applications requiring inser-
tion, deletion, and key range searches. They are used to implement most modern
file systems. B-trees address effectively all of the major problems encountered
when implementing disk-based search trees:
1. B-trees are always height balanced, with all leaf nodes at the same level.
2. Update and search operations affect only a few disk blocks. The fewer the
number of disk blocks affected, the less disk I/O is required.
3. B-trees keep related records (that is, records with similar key values) on the
same disk block, which helps to minimize disk I/O on searches due to locality
of reference.
4. B-trees guarantee that every node in the tree will be full at least to a certain
minimum percentage. This improves space efficiency while reducing the
typical number of disk fetches necessary during a search or update operation.
Search WWH ::




Custom Search