Why do some search trees store all the elements in leaves, while others don't?

Question

1. Why do some search trees store all elements in the leaves, while other search trees don't? One difference that makes is whether a successful search may end up in an internal node.

   For m-ary search trees, the former case will need more leaves and more heights than the latter. Is this the benefit of not storing all the elements in the leaves?

   Is storing all the elements in the leaves only for looking consistent? Does it have some benefits? Someone said that

   Contrary to what you said, in the three examples you gave, the internal nodes also contain values.

   In a B+ tree for example, all values are located in the leaves, the internal nodes only contains keys

   "This is interesting only when the data is separated in a key and some other value (as in a database). This allows more keys to go in the internal nodes, limiting the tree depth. When the nodes are on a slow medium, this limits the time needed to go to the data." But I don't quite understand that, because

   • when we choose to store records in the internal nodes, we don't need to store the actual records in the internal nodes, but can always store with each key a pointer to the actual records, so that we can save space to store more keys. So I don't understand why he said that "This allows more keys to go in the internal nodes".

   • as mentioned above, I guess storing elements in the leaves rather than also in internal nodes will make the search trees higher, so I don't understand why he said that storing all the elements in the leaves can "limit the tree depth".

2. For B-trees and 2-3 trees, why do some references define them so that all the elements are stored in the leaves, while other references don't? Note that 2-3 trees are special B-trees, according to Aho's book.

   I just found that

   • the definitions of 2-3 trees and B trees in Aho's Data Structures and Algorithms store all the elements in the leaves, so that a successful search always end up in a leaf

   • But the examples of 2-3 trees and B trees in Wikipedia and also in wikipedia and in Sedgewick's Algorithms (also see the first picture below) and in CLRS (see the second picture below) store only some elements in the leaves, so that a successful search may end up in an internal node.

     
     

3. For binary search trees, why all the references define them so that not all elements are stored in the leaves?

   I haven't seen any reference that define binary search trees with all elements defined in the leaves, or am I missing it?

   Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?

4. Is balancing the only or most important aspect where 2-3 trees improves over binary search trees?

   From the above questions, I mentioned that some references define 2-3 trees so that all the elements are stored in the leaves, while others don't, and within my readings, binary search trees are always defined so that not all the elements are stored in the leaves. Is whether search trees store all elements in the leaves an important aspect to distinguish between 2-3 trees and binary search trees, as important as the balancing aspect?

Thanks.

Answer 1

The point is that often data is bulky and moreover of variable size (i.e., a full student record) while the keys needed to locate the data (name, enrollment number) is small and fixed size. Different requirements, keep them separate.

Answer 2

There are a lot of questions in here, and I'm going to pick out a few that may help answer your questions.

Why do some search trees store all elements in the leaves, while other search trees don't?

Others have mentioned the difference between B-trees and B+-trees. For databases specifically, B+-trees have a huge advantage over B-trees: they support range queries more efficiently.

Consider a SQL statement such as:

SELECT something FROM table
WHERE field >= 10 AND field < 20;

Suppose also that there is a B+-tree index on field, where the leaf nodes are connected (e.g. they form a doubly-linked list) in addition to the tree above them. Then one way to satisfy this query is to search for the value 10 in the index, and then traverse the leaf nodes.

With B-trees, you would have to traverse up and down the tree, which involves accessing (and, in a concurrent environment, locking) more nodes/disk pages.

Can Huffman trees be viewed as binary search trees where all the elements are defined in the leaves?

Huffman trees usually aren't binary search trees. In binary search trees, an inorder traversal results with the leaves ordered according to "less than" ordering. In Huffman trees, that is usually not the case.

Consider the following frequency distribution over the following alphabet:

A     1
B     8
C     1

Any valid Huffman tree must have a node with A and C as children. But A < B < C. So you cannot have a Huffman-shaped binary search tree for this frequency distribution.

(Having said that, some applications of Huffman trees remap the alphabet into increasing or decreasing frequency order. See, for example, canonical Huffman codes or Wavelet trees.)

Is balancing the only or most important aspect where 2-3 trees improves over binary search trees?

Probably not even that. Research is fairly consistent that any balancing scheme for binary search trees is as good as any other. The purpose of balancing BSTs is to avoid pathological behaviour (i.e. "sticks"), and so a choice of balancing scheme should be based on criteria other than how well it balances.

Answer 3

You mention that "2-3 trees are special B-trees". Note that B-trees are different from B+-tree. In a B-tree, internal nodes also store part of the keys, while in a B+-tree, keys are all stored in the leaves. Therefore, 2-3 trees, as B-trees of order 3 by definition, can have elements in their internal nodes.