3
$\begingroup$

According to Wikipedia B-tree page, Knuth's definition fifth property is "All leaves appear in the same level and carry no information.".

What does it mean that they carry no information?

Does that mean that there are no more pointers to children nodes? (kinda redundant to say that as they are the leaves no?)

In the more literal meaning I understand from it that there is actually no information there (AKA the nodes values vs. the key which is used to search) but that doesn't make sense as each key in a B-tree appear only at one node and thus must have a value associated to it or at least a pointer to the data.

Please notice that I'm not referring to a B+ tree where indeed there is an extra layer just for the data/values/information and the keys are indeed duplicated between nodes levels.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ The explanation in en.wikipedia reads In Knuth's terminology, leaf nodes do not carry any information. The internal nodes that are one level above the leaves are what would be called "leaves" by other authors: these nodes only store keys (at most m-1, and at least m/2-1 if they are not the root) and pointers to nodes carrying no information.; I would add/insinuate that all internal nodes store keys, only. $\endgroup$
    – greybeard
    Sep 26, 2020 at 17:14
  • $\begingroup$ Yeah I read that few times (and the entire page) but it didn't help :) The only way I can see how it work is that the leaves are just singular records of data (each searched item got its own leaf), but isn't that the B+ tree variant? $\endgroup$
    – Nimrod Yonatan Ben-Nes
    Sep 27, 2020 at 6:34
  • $\begingroup$ B+ tree definitions seem to disagree, some specifying all keys are present in the leaves and replicated above (oops - as described at the bottom of the question). I don't think the term B+ tree likely to have been coined in 1973 when TAoCP vol.3 was published - Bayer/McCreight's paper being from '72; Knuth puts their B-tree concept in '70. $\endgroup$
    – greybeard
    Sep 27, 2020 at 7:34
  • $\begingroup$ Well maybe there is confusion between the 2 but they still are supposed to different... I think anyway... According to Wikipedia page on B+ tree "A B+ tree can be viewed as a B-tree in which each node contains only keys (not key–value pairs), and to which an additional level is added at the bottom with linked leaves. " which fit what I said above but does not fit to a B-tree, and if at a B-tree each node got key-value pair AND leaf nodes do not have keys we get to a situation that leaf nodes do not carry values as well... so what is the point of having them at all? $\endgroup$
    – Nimrod Yonatan Ben-Nes
    Sep 27, 2020 at 13:47

1 Answer 1

Reset to default
1
$\begingroup$

So according to CLRS (quotations):

  • Any "satellite information" associated with a key is stored in the same node as the key
  • Leaf nodes have no children, so their ci fields [pointers to child nodes, added for clarification] are undefined
  • A common variant on a B-tree, known as a B+-tree, stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes

There was no mention about leaf nodes carrying no keys/information/etc...

So basically leaf nodes do carry keys in order to actually get the data you search for (just like all the other nodes), they just don't carry pointers to child nodes.

And why Donald Knuth wrote (according to Wikipedia and other sources) that leaf nodes "carry no information" is beyond me, maybe he was referring to a different variant of B-tree... I honestly don't know.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.