Indexing and B+ Trees

An index is a data structure that speeds up lookups on a column, like the index at the back of a book.

Index type	Description
Primary (clustered)	Built on the ordering key of a sorted file; at most one per table
Secondary (non-clustered)	On a non-ordering field; many allowed
Dense	An index entry for every search-key value
Sparse	Entries for only some values (e.g. one per block)
Multilevel	Index on an index, which reduces disk accesses

B+ Tree

A balanced tree: all leaves are at the same level.
Internal nodes store only keys (for navigation); all data pointers are in the leaves.
Leaves are linked, so range queries are fast.
A node of order p has at most p children and at least ⌈p/2⌉ (except the root).
Search, insert and delete take O(log n).

Text

                [ 30 | 60 ]
              /      |      \
     [10|20]    [30|40|50]    [60|70|80]
        ↔            ↔             ↔        (linked leaves)

B Tree vs B+ Tree

B Tree	B+ Tree
Data pointers in all nodes	Data pointers only in leaves
No duplicate keys	Internal keys repeated in leaves
Leaves not linked	Leaves linked (good for ranges)

SQL

CREATE INDEX idx_student_name ON Student(name);

Track your progress through the DBMS course

← Prev