CODEWITHSUNDEEP
data-structureskeydefinitionb-tree
Govind Parmar
Govind Parmar

Reputation: 21532

What exactly does "key" mean, in the context of B-Trees?

Say we have a B-Tree with the following structure:

           [5] [10]
          /   |    \
    [1][2]  [6][8]  [11][14]

Is it appropriate to say that 5 and 10 are the "keys" for the buckets at the bottom of the tree? Or am I totally missing the definition of "keys" for B-trees?

Upvotes: 4

Views: 9127

Answers (3)

GraceMeng
GraceMeng

Reputation: 1099

I would prefer to say 5 and 10 are the "keys" of the root.

A b-tree node can be defined as below:

class Node {
    Integer[] keys;
    Node[] children;
    // constructor ...
}

So the root [5] [10] is a node with 3 children, containing keys 5 and 10.

Upvotes: 1

templatetypedef
templatetypedef

Reputation: 372714

Generally, tree structures store a collection of values called keys. In the above tree, all the listed numbers are keys. He term keys is appropriate since trees often store key/value pairs and the balancing and lookup logic only applies to keys.

Hope this helps!

Upvotes: 5

Thilo
Thilo

Reputation: 262474

Wikipedia says:

Each internal node of a B-tree will contain a number of keys. The keys act as separation values which divide its subtrees.

So, yes, that would be the definition of "keys" for B-trees.

Upvotes: 1

Related Questions