Recent Post

B+ Tree

B+ tree is used for storing the records efficiently by storing then in an indexed manner using the B+ Tree indexing Structure.

Description :-  

 A B+ Tree is also known as a Balanced Tree- in which every path from the root of the tree to a leaf of the tree is of the same length.

A B+ Tree index is a multi-level index, but it has a structure that differs from that of the multi-level index-sequential file.

B+ Tree Node Structure :-

It contains up to n-1 search key values (k1 to kn-1) & n pointers (p1,p2,....,pn).

Search key values within a node are kept in sorted order ; thus if i < j , then ki < kj

Special Case :-

Root node is the only node in the tree.
→ i.e. Root node becomes the leaf node.
Minimum number of children → 1 → Pointing to the only single list of Records.
Maximum number of children → b-1 → Same as that of a leaf Node. 

Constraints on various types of Node

Let 'b' be the branching factor or order of B+ tree.
NON-LEAF NODE :- Let m represent the no. of children of a node.
[b/2] ≤ m ≤ b
Let k represent the no. of search keys in a node.

Leaf Nodes occurring at the last level of the B+ tree use their one pointer (last one) to connect with each other to facilitate the sequential access at leaf level.
Max. no. of children :-
         [b/2] - 1 ≤ m ≤ b-1             (pointers remain same)
Max. No. of search keys :-
         [b/2] - 1≤ k ≤ b-1
[ Since no. of pointers are same, only one of them in each node is used for connecting each among leaf nodes.]

Root NODE :-
Max. no. of children 
  ⟶ b ( connected as internal node only)

Min. no. of children ⟶2 
       2 ≤ m ≤ b                            [ It must have at least 2 pointers in case it has only one search key]

No comments