B+ trees structure of leaf and internal nodes

Example:

Search key field is 9 bytes the block size is 512bytes , a record pointer pr 7 bytes , a  block pointer is 6 bytes. What is the order of internal node and leaf .

Solution:

For internal node:-

n*(block pointer) +(n-1)(search key) ≤ 512

n*6 + (n-1)*9  ≤ 512

15n ≤ 521

n ≤ 34.73

order of internal node =34

For leaf node:

Oleaf*(K+pr) + block pointer  ≤ 512

 

Oleaf(7+9) + 6  ≤512

16*Oleaf    ≤ 506

Oleaf  ≤ 506/16

Oleaf  =31

 

 

 

 

Contributor's Info

Created:
0Comment
Under flow and Overflow in the B-trees

while insertion we get overflow and during deletion we face underflow situation.

let the order of b tree is 'p'

Condition for Root node:

in case of Min       ----------- 2 tree pointer

                                                     1 key entry

in case of Max      ----------- 'p' tree pointer

                                  ------------- p-1 key entry

 

Condition for Internal node:

n case of Min       ----------- ceil(p/2) tree pointer

                                                    ceil(p/2)-1  key entry

in case of Max      ----------- 'p' tree pointer

                                  ------------- p-1 key entry

Condition for leaf node:

in case of Min       ----------- ceil(p/2)-1  key entry

in case of Max      ----------- 'p-1' key entry

 

 

Example:let order p=5, now find min and max for all nodes

Solution

Root:

in case of Min       ----------- 2 tree pointer

                                                     1 key entry

in case of Max      ----------- '5' tree pointer

                                  ------------- 4 key entry

 

nternal node:

n case of Min       ----------- ceil(5/2) =3 tree pointer

                                                    ceil(5/2)-1 = 2 key entry

in case of Max      ----------- '5' tree pointer

                                  ------------- 4 key entry

 

leaf node:

in case of Min       -----------   ceil(5/2)-1 = 2 key entry

in case of Max      ----------- 4 key entry

Contributor's Info

Created:
0Comment
Properties of B-trees

Properties of B trees :

 

Example:

In a B tree ,suppose search key is 9 bytes long, disk block size is 512 bytes, record pointer is 7bytes, Block pointer is 6bytes, then calculate the order of B tree node.

 

Soluton:

n*p + (n-1)(k+pr) ≤Block size

n*6 +(n-1)16 ≤ 512

22n -16 ≤ 512

22n ≤ 528

n ≤ 528/22

n ≤ 24

where n is order of b tree

Contributor's Info

Created:
0Comment
Type of indexing

Indexing can be classified into two parts as

1)Single Level Index: this is again divides into three parts :

a)Primary index :(PK +Ordered) A primary index is an ordered file whose records of fixed length with two fields. The first field is same as  primary key (PK)of data file and the second is a pointer to a data block, where the key is avialable.

  1. index created for the first record of each block called 'block anchors'.
  2. The no. of index entries equal to no of data blocks.
  3. The average no of block access using index=log2 Bi +1 where Bi is block number.

b)Clustered Index: (NK+Ordered) Clustering index is created on the data file whose file record are physically ordered on non key(NK) field which does not  have  distinct  value  for each record, that field is called as clustering field.

    1. The average no of block access using index=log2 Bi +1 where Bi is block number.

c)Secondary Index(NK/CK + Un-Ordered)  Along with primary index if you have one more index then problem is ,that  perticular index will not be in sorted order it means that it is unordered , So it is called secomdary index.

   here we can say primary indexing is usefull when the search is based on the primary key.

If you have many search request which are based on something else other than primary key then it is better to make index for that particular key also.

  1. Secondary index may be a non key or candidate key
  2. Index entry is created for each for each ecord in a data file
  3. no of index entries = no of record

2)Multi Level Index: here we have B tree and B+tree 

you can think B tree and B+ tree as multilevel index means we can insert the nodes ,delete the node and change the level dynamically.

we have two pointer for storing the file and they are:

1)Node pointer or block pointer 

2)Record pointer 

we may have a doubt  that,why we use B-tree and B+-tree instead of Avl or R B tree and many more?

Reason for this doubt can be understand as, Avl tree or Red black tree they grow in vertically while In B and B+tree ,you can keep the height smaller and we can store as much as data as possible

            Using B,B+ tree we reduced the level therefore we reduce the time complexity.

 

Contributor's Info

Created:
0Comment