4,890 views
5 votes
5 votes

Consider a DBMS that has the following characteristics:

  • 2KB fixed-size blocks
  • 12-byte pointers
  • 56-byte block headers

We want to build an index on a search key that is 8 bytes long. Calculate the maximum number of records we can index with

a) a 3-level B+ tree (2 levels plus the root)

b) a 3-level B tree

3 Answers

3 votes
3 votes

Given :

Block Size = 2KB = 2048 Bytes.

Block Header Size = 56 Bytes. (Block Header is some space, here 56 Bytes, reserved in each block that contains data about that Block)

So, The Actual Available Block Space/Size for database Records or index records or our desired datain every Block is $2048 - 56 = 1992 \,\, Bytes$

Pointer size = 12 Bytes (So ALL the pointers i.e. Data/Record Pointer or Node/Tree/Block Pointer are of size 12 Bytes)

Search key size = 8 Bytes


For B+ Tree : 

Let each node of  B+-tree contain at most $n$ pointers and hence at most $n-1$ keys. $8 \times (n-1) + 12 \times n <= 1992 .$ Therefore, $n <= 100.$

Since in B+ Tree, The Pointers to Database Records (i.e. Data/Record Pointers) are only present at Leaf level. So, to find "maximum number of records we can index", we need to find the number of Record/Data Pointers(which is equal to the number of keys) in the leaf nodes collectively. 

The leaf level of B+-tree can hold at most 100 * 100 * 99 record pointers. Therefore, the maximum number of records that can be indexed is 990000.


For B Tree :

Let each inner node of a B-tree contain at most $n$ index pointers, $n-1$ keys, and $n-1$ record pointers. $12 \times n + (n-1)(8+12 \leq 1992).$ Therefore, $n <= 62.$

Since in B Tree, The Pointers to Database Records (i.e. Data/Record Pointers) are present at ALL levels. So, to find "maximum number of records we can index", we need to find the number of Record/Data Pointers(which is equal to the number of keys) in the All the levels collectively. 

The first level of a B-tree can hold at most 61 record pointers. The second level can hold at most 62 * 61 record pointers. The leaf level can hold at most 62 * 62 * 61 record pointers. Therefore, the maximum number of records that can be indexed is 61 + 62 * 61 + 62 * 62 * 61 = 238327.

http://infolab.stanford.edu/~nsample/cs245/handouts/hw2sol/sol2.html


Block Header : data at beginning of the block that describes block.

It May contain :

- File ID (or RELATION or DB ID)

- This block ID

- Record directory

- Pointer to free space

- Type of block (e.g. contains recs type 4; is overflow, …)

- Pointer to other blocks “like it”

- Timestamp ...

etc

http://www-db.stanford.edu/~hector/cs245/Notes03.pdf


 

0 votes
0 votes
a. In B+ tree,

Order of internal node is 31 and order of leaf node is 99

So total number of keys 31*31*99 = 87451.

b. In B -tree,

order is 27.

total number of keys = (27^3) -1 = 19682
0 votes
0 votes

For B tree

We need to Calculate Order of tree (i.e. maximum no. of child's a Node can have):

Assume,

n: order  
K : Key pointer (8 Bytes)
Pr :Record Pointer (12 Bytes)
P: Block Pointer / Tree Pointer (56 Bytes)
BS: Block Size (2KB or, 2048 Bytes)

$n * (P) + (n - 1) * (K + Pr) \leq 2048$

$\Rightarrow 56n + 20n - 20 \leq 2048$

$\Rightarrow n \leq 27.21$

$\Rightarrow n = 27$

First-Level can have $26$ index records, Second-Level can have $26 * 27$ index records (coz First-Level can have a maximum of $27 $ Child, and each child can have $27$ Child, further. Hence, each Child at Second-Level can have $26$ index records), Third-Level can have $26 * 27 * 27$ index records.

$Answer = 26 + 26 * 27 + 26 * 27 * 27$

For B+ tree,

We need to find Order of tree for both, non-leaf (i.e. Root or Internal) and leaf nodes.

edited by

Related questions

0 votes
0 votes
1 answer
1
Vishnathan asked Aug 24, 2018
8,176 views
1 votes
1 votes
2 answers
3
Ayush Upadhyaya asked Mar 20, 2017
1,006 views
Searching and retrieval of data is more efficient using which tree?B Tree or B+ Tree?
18 votes
18 votes
1 answer
4
Akanksha Kesarwani asked Dec 10, 2016
6,279 views
Difference between left biasing and right biasing in B+ tree insertion, Rules to be followed for left and right biasing , Kindly explain with an example ?