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