3
CRLS (Introduction to the Algorithms, Cormen et al) defines that the keys of a node in a B-Tree must be in non-degressing order (K1 <= K2 <= ... <= Kn). However, as there is no repetition of keys, this order should be strictly increasing (so, too, state Bayer and Mcgreight in their 1972 article). That is correct?
1
B-Tree is a kind of generalization of the binary tree, where the nodes are grouped into pages and each of them can point to several others. Its properties make it ideal to work with disks, as it minimizes the most expensive operations (turn the disk and move the head, ie start reading a block).
When Bayer and Mcgreight wrote their article they were not interested in what types of data would be stored by these trees. The goal was to define the tree theoretically, show access times, write and delete times, and present important calculations and algorithms. But after 1972 it began to be used and over the years the term was applied somewhat outside the original definition.
B-Trees are widely used in databases and other ways to store large amounts of data on a disk. In some circumstances having repeated keys can be an advantage, since the time to eliminate them can be very high. But this causes several problems, especially in deletion.
Imagine that the same key is repeated several times and you want to delete one of the elements that was stored with that key. It’s going to take walking through all the occurrences of that key until you find the specific element, which will be very inefficient.
Usually when a B-Tree contains repeated keys one more attribute is added to make a composite key so that it is unique. Thus, some operations can use the normal key and others the composite key. Another solution is to keep a separate index that manages all repeated keys.
Anyway, in the article it was better to consider that the keys are unique, because then the whole theory would get more elegant, treating cases of repeated keys would not be interesting. But in practice there are cases where it is better to use a B-Tree with not unique keys allowed and solve the resulting problems in other ways. No wonder people will stop calling it B-Tree.
Soon Cormem’s book preferred to define the B-Tree this way, not to exclude those cases where the key is not unique and which can be used in practice.
Browser other questions tagged tree
You are not signed in. Login or sign up in order to post.