I would like to know what are the differences between (a,b)-tree and a B-tree. It has been a few days I am studying different papers and I am seeing different definitions that make me confused.

For example in External Memory geometric Data Structure by Lars Arge on Page 3 he says

Normally, the N data elements are stored in the leaves (in sorted order) of an (a; b)-tree T , and elements in the internal nodes are only used to guide searches.

So the N data elements are stored in the leaves and internal nodes are only used to guide searching, they don't contain any data element other than the leaves. While in B-trees it is not so, In B-tree internal nodes contain their own different elements and every element of an internal node is used as a separator of its children. In fact it is a data element that is moved up. Like this

enter image description here

But from (a,b) Trees, it says

A B-Tree is a (a,b)-tree with a = ceil(b/2).

Which is in contradiction with the structure of internal nodes, Furthermore it shows that internal nodes have different elements than the leaves and all of the elements are not stored in the leaves. They may be stored in the internal nodes as well. In the insertion phase, some of the elements of the nodes are moving up to the parent as the separator.

I would like to know what are the elements in the internal nodes of B-trees and (a,b)-trees?

Thanks in advance.


1 Answer 1


It seems you are right. The author probably takes as a standard definition the B+-tree where internal nodes are used as separators.

You should always be prepared for authors that deviate from standard definitions and naming conventions!

  • $\begingroup$ Then (a,b) tree and B tree both can have data elements in internal nodes, right? $\endgroup$
    – M a m a D
    Feb 14, 2016 at 3:37

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.