# B+ Tree

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

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.

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.

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.

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

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