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 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]
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 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