Review of Trees - Database Systems - page 453

A possible implementation of a B-tree of LibraryPatron objects is shown in
Figure A1-24 . As you may well imagine, maintaining such a tree is much more challenging
than a BST or heap, but by no means insurmountable. We will look more closely at some
of these algorithms shortly.
Figure A1-24a. The UML Diagram of the PatronBTNode Class
Figure A1-24b. The UML Diagram of the PatronsBTree Class
Sequential search of the B-tree is achieved by an In-order traversal. Several values
may be sought simultaneously. Note however, that internal nodes will be visited more
than once since they contain several keys. Performance is therefore poor.
The direct search algorithm is shown in Figure A1-25 . It is used to find a specific node
in the tree. It is a very efficient algorithm. On the average, searching for an item among
1,000,000 items takes just about 20 comparisons! B-trees are also excellent for storing large
volumes of data without deteriorating. For these reasons, B-trees are widely used as the file
systems for compilers, database management systems, and operating systems.