CODEWITHSUNDEEP
b-tree
fmunshi
fmunshi

Reputation: 415

Maximum and minimum number of keys in this B-tree

This is from a homework assignment:

Assume that each page (disk block) has 16K bytes and each KVP has 8 bytes. Thus we decide to use a B-tree of minsize (16000/8)/2 = 1000. Let T be such a B-tree and suppose that height of T is 3. What is the minimum and maximum number of keys that can be stored in T? Briefy justify your answer.

Note the following due to the properties of B-trees:
Each node has at most 2000 keys
Each node has at least 1000 keys (except for the root node)

I am having trouble understanding how the memory is limiting the number of keys. It seems to me that since each page has 16000 bytes of space and each key takes up 8 bytes, then each page can store 2000 keys which is the max number of keys that can be stored at each level anyways.

The following are my calculations:
Minimum number of keys = 1000(1001)(2) + 1 = 2002001 keys at minimum
(Since the root is not constrained to having at least 1000 keys)
Maximum number of keys = 2000(2001)(2001) = 8008002000 keys at maximum

I feel I am missing something vital as the question cannot be this simple.

Upvotes: 1

Views: 3004

Answers (1)

JimR
JimR

Reputation: 16123

Somewhat blatant hint: Each non-leaf node has a right and a left child. Plus, there are pointers to key/value pairs, however they might be stored. (1000 seems like a lot...) Think about how you're going to store those 1000+ data points.

+--------------+
|     Root     |
| Left   Right |
+---+------+---+
    |      |
    |  +---+----------+
    |  |   Level 2    +---Data: List, hash table, whatever
    |  | Left   Right |
    |  +---+------+---+
    |      |      |
    |      Etc    Etc
    |
+---+----------+
|   Level 2    +---Data: List, hash table, whatever
| Left   Right |
+---+------+---+
    |      |
    Etc    Etc

Upvotes: 2

Related Questions