🌳 MULTILEVEL INDEXING USING B-TREE & B+ TREE
Hierarchical Indexing • Searching • Insertion • Deletion • Tree Visualization
📘 What is Multilevel Indexing?
When a database file becomes very large, a single-level index can itself become too large to search efficiently. The solution is to create an index on the index. This produces multiple levels of indexing.
B-Tree and B+ Tree are important balanced tree structures used to implement efficient multilevel indexing.
When a database file becomes very large, a single-level index can itself become too large to search efficiently. The solution is to create an index on the index. This produces multiple levels of indexing.
DATA FILE
↓
LEVEL 1 INDEX
↓
LEVEL 2 INDEX
↓
LEVEL 3 INDEX
↓
RECORD
Idea:
Instead of searching thousands of index entries directly,
the DBMS moves through a small number of levels.
B-Tree and B+ Tree are important balanced tree structures used to implement efficient multilevel indexing.
🌳 Multilevel Indexing
Multilevel indexing organizes indexes into several levels.
The top level points to lower-level index blocks, and the
lowest level points to data blocks.
LEVEL 2 INDEX
```
[ 50 | 100 ]
/ \
/ \
```
LEVEL 1 INDEX
```
[10|20|30] [60|70|80]
| |
↓ ↓
```
DATA BLOCKS
[10][20][30] [60][70][80]
The tree remains balanced, so the number of levels remains
small even when the database contains a large number of
records.
📚 How Multilevel Indexing Works
If an index becomes too large to fit efficiently into a
small number of blocks, another index level can be created
over it.
This process can continue until the top-level index is small
enough to access efficiently.
Example
10,000 DATA RECORDS
↓
100 INDEX BLOCKS
↓
10 HIGHER-LEVEL INDEX BLOCKS
↓
1 ROOT BLOCK
1
Create an index for the data blocks.
2
If this index is still large, create another index over it.
3
Continue until a small top-level index is produced.
4
Search begins at the top and moves downward.
ROOT
↓
INDEX LEVEL
↓
INDEX LEVEL
↓
DATA
🌲 B-Tree
A B-Tree is a balanced multiway search tree.
Each node can contain multiple keys and multiple child
pointers.
All leaf nodes are at the same depth.
Important Properties
✔ Balanced tree
✔ Multiple keys can exist in one node
✔ A node can have multiple children
✔ All leaves occur at the same level
✔ Searching, insertion and deletion remain efficient
✔ Multiple keys can exist in one node
✔ A node can have multiple children
✔ All leaves occur at the same level
✔ Searching, insertion and deletion remain efficient
Simple B-Tree
```
[ 30 | 60 ]
/ | \
/ | \
[10|20] [40|50] [70|80|90]
```
The root contains separator keys and internal nodes may also contain keys that represent actual searchable values.
🌿 B+ Tree
A B+ Tree is a balanced multiway tree in which
actual data-record pointers are stored at the leaf level.
Internal nodes mainly contain search keys and child pointers.
The leaf nodes are linked, making sequential and range
processing efficient.
Simple B+ Tree
```
[ 30 | 60 ]
/ | \
/ | \
[10|20] → [30|40|50] → [60|70|80|90]
↑ ↑ ↑
DATA DATA DATA
```
Key idea:
Internal nodes guide the search.
Leaf nodes contain the data pointers.
Leaf nodes are linked for efficient sequential access.
Leaf nodes contain the data pointers.
Leaf nodes are linked for efficient sequential access.
📋 B-Tree Example
Consider inserting:
10, 20, 30, 40, 50, 60, 70
Final simplified B-Tree
```
[ 40 ]
/ \
/ \
[10|20|30] [50|60|70]
```
The root separates the smaller keys from the larger keys.
The tree remains balanced.
📋 B+ Tree Example
Consider the keys:
10, 20, 30, 40, 50, 60, 70, 80
Example B+ Tree
```
[ 30 | 50 | 70 ]
/ | | \
/ | | \
[10|20] → [30|40] → [50|60] → [70|80]
```
The leaf nodes are connected:
[10|20] → [30|40] → [50|60] → [70|80]
This makes sequential traversal and range searches efficient.
[10|20] → [30|40] → [50|60] → [70|80]
This makes sequential traversal and range searches efficient.
🔍 Searching in a B-Tree
Search for 60.
```
[ 40 ]
/ \
/ \
[10|20|30] [50|60|70]
```
1
Start at the root: [40].
2
60 is greater than 40.
3
Move to the right child.
4
Search [50|60|70].
5
60 is found.
60
↓
40
↓
50 | 60 | 70
↓
FOUND
🔎 Searching in a B+ Tree
Search for 60.
```
[ 30 | 50 | 70 ]
/ | | \
[10|20] → [30|40] → [50|60] → [70|80]
```
1
Start at the root.
2
Compare 60 with separator values.
3
Move to the leaf containing values 50 and 60.
4
Search inside the leaf.
5
60 is found.
ROOT
↓
[30 | 50 | 70]
↓
[50 | 60]
↓
60 FOUND
➕ B-Tree Insertion
Insert the following keys:
10, 20, 30, 40, 50
Step 1
[10]
Step 2
[10|20]
Step 3
[10|20|30]
Step 4 — Split when required
```
[20]
/ \
[10] [30]
```
Step 5 — Insert 40
```
[20]
/ \
[10] [30|40]
```
Step 6 — Insert 50
```
[20]
/ \
[10] [30|40|50]
```
The exact split point depends on the chosen B-Tree order.
The example illustrates the basic splitting concept.
➕ B+ Tree Insertion
Insert keys into a simplified B+ Tree.
10, 20, 30, 40, 50, 60
Initial
[10|20|30]
Insert 40 — Leaf Split
```
[30]
/ \
[10|20] → [30|40]
```
Insert 50
```
[30]
/ \
[10|20] → [30|40|50]
```
Insert 60 — Another Split
```
[30|50]
/ | \
[10|20] → [30|40] → [50|60]
```
The leaf nodes remain linked after splitting.
🗑️ B-Tree Deletion
Deletion from a B-Tree must preserve the minimum-key and
balance properties of the tree.
If deletion causes a node to have too few keys, the tree may
redistribute keys or merge nodes.
Example
```
[40]
/ \
[10|20] [50|60]
```
Delete 60.
1
Locate key 60.
2
Remove 60 from its node.
3
Check whether the node still satisfies the minimum occupancy requirement.
4
If necessary, redistribute or merge nodes.
Deletion rules depend on the order of the B-Tree.
🗑️ B+ Tree Deletion
B+ Tree deletion removes the key/data pointer from the leaf.
If a leaf becomes underfull, redistribution or merging may
be required.
Internal separator keys may also need updating.
```
[30|50]
/ | \
[10|20] → [30|40] → [50|60]
```
Delete 60.
1
Locate 60 through the root.
2
Move to the appropriate leaf.
3
Delete 60 from the leaf.
4
Check minimum occupancy.
5
Redistribute or merge if required.
The leaf-level linked structure must remain valid.
🏗️ Structure of B-Tree and B+ Tree
| Component | B-Tree | B+ Tree |
|---|---|---|
| Root | Contains keys and pointers | Contains separator keys and pointers |
| Internal Nodes | May contain search keys/data references | Mainly contain search keys and child pointers |
| Leaf Nodes | Contain keys and possibly data references | Contain keys and data-record pointers |
| Leaf Linking | Not a defining feature | Leaf nodes are linked |
| Range Search | Good | Very efficient |
⚖️ B-Tree vs B+ Tree
| Feature | B-Tree | B+ Tree |
|---|---|---|
| Data Location | Can appear in internal and leaf nodes | Stored/referenced at leaf level |
| Internal Nodes | Keys and possibly data references | Keys and child pointers |
| Leaf Nodes | Not necessarily linked | Linked together |
| Sequential Access | Good | Very efficient |
| Range Queries | Good | Excellent |
| Search Path | May finish at an internal node | Search normally proceeds to a leaf |
| Database Indexing | Possible | Very commonly used |
⭐ Advantages
Multilevel Indexing
✔ Reduces search time
✔ Reduces the number of disk accesses
✔ Suitable for very large files
✔ Provides hierarchical access
B-Tree / B+ Tree
✔ Balanced structure
✔ Efficient search
✔ Efficient insertion and deletion
✔ Handles large amounts of data
✔ Height remains relatively small
✔ B+ Tree is excellent for range and sequential access
✔ Reduces search time
✔ Reduces the number of disk accesses
✔ Suitable for very large files
✔ Provides hierarchical access
B-Tree / B+ Tree
✔ Balanced structure
✔ Efficient search
✔ Efficient insertion and deletion
✔ Handles large amounts of data
✔ Height remains relatively small
✔ B+ Tree is excellent for range and sequential access
⚠️ Disadvantages
❌ Tree structures require additional storage.
❌ Insertions and deletions require structural maintenance.
❌ Node splitting can occur during insertion.
❌ Node merging or redistribution can occur during deletion.
❌ Index structures must be maintained when records change.
❌ Insertions and deletions require structural maintenance.
❌ Node splitting can occur during insertion.
❌ Node merging or redistribution can occur during deletion.
❌ Index structures must be maintained when records change.
🏫 Complete Multilevel Indexing Example
Suppose a database contains Student_ID values:
10, 20, 30, 40, 50, 60, 70, 80, 90
Level 1 — Data
[10|20|30] → [40|50|60] → [70|80|90]
Level 2 — Index
```
[40|70]
/ | \
↓ ↓ ↓
Block1 Block2 Block3
```
Search for 80
1
Start at the upper index.
2
80 is greater than 70.
3
Follow the pointer to Block 3.
4
Search Block 3.
5
80 is found.
80
↓
INDEX
↓
BLOCK 3
↓
80 FOUND
B+ Tree Representation
```
[40|70]
/ | \
/ | \
[10|20|30] → [40|50|60] → [70|80|90]
```
The upper level guides the search, while the leaf level
contains the searchable data entries and links them for
sequential access.
❓ Important Questions & Answers
Q1. What is multilevel indexing?
Multilevel indexing creates multiple levels of indexes.
A higher-level index points to lower-level indexes, and
the lowest level provides access to the data blocks.
Q2. Why is multilevel indexing required?
It is required when a single-level index becomes too large
to search efficiently. Multiple levels reduce the amount of
index data examined at each stage.
Q3. What is a B-Tree?
A B-Tree is a balanced multiway search tree in which nodes
can contain multiple keys and children, with all leaf nodes
at the same depth.
Q4. What is a B+ Tree?
A B+ Tree is a balanced multiway tree in which internal
nodes primarily contain search keys and child pointers,
while data-record pointers are stored at the leaf level.
Leaf nodes are linked.
Q5. What is the main difference between B-Tree and B+ Tree?
In a B-Tree, searchable data references may occur in internal
as well as leaf nodes. In a B+ Tree, data-record references
are maintained at the leaf level, while internal nodes guide
the search.
Q6. Why are B+ Trees useful for range queries?
After finding the first relevant leaf, the DBMS can follow
the linked leaf nodes to retrieve subsequent values efficiently.
Q7. Why must B-Trees remain balanced?
A balanced tree keeps all leaf nodes at the same depth,
preventing one search path from becoming much longer than
another.
Q8. What happens when a B-Tree node overflows?
The node can be split and a separator key can be promoted
to the parent. This may propagate toward the root.
Q9. What happens when a B+ Tree leaf overflows?
The leaf can be split into two nodes, and a separator key
is inserted into the parent. The leaf-level linked structure
is maintained.
Q10. What happens during deletion?
If deletion causes underflow, the tree can redistribute keys
with a neighboring node or merge nodes, depending on the
specific tree rules.
Q11. Which is better for sequential access: B-Tree or B+ Tree?
B+ Tree is generally better because its leaf nodes are linked,
allowing efficient sequential traversal.
Q12. What is the major advantage of B+ Tree indexing?
It provides efficient search together with particularly
effective sequential and range access through linked leaves.
No comments:
Post a Comment