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".
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
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.
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?
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?