A table with ten million rows and no index forces the database to scan every row to answer one lookup. An index turns that linear scan into a handful of disk reads. B+ trees are the structure that makes this happen, and they appear in almost every DBMS exam. Let us build the idea from why indexing exists up to a B+ tree insert you can draw by hand.
Why indexing at all
A database stores rows on disk in blocks, and a disk read is thousands of times slower than a memory access. Without an index, finding one row means reading every block, an O(N) scan. An index is a smaller, ordered structure mapping a search key to the location of the matching row, so the database can navigate to the row in far fewer block reads. The index is itself stored on disk, so the goal is to make it shallow: fewer levels means fewer disk reads.
Dense versus sparse indexes
A dense index has one index entry for every search-key value in the data file. Lookup is direct, but the index is large.
A sparse index has one entry per data block, pointing to the first record of that block; to find a key, you locate the largest index entry not exceeding your key, then scan within that block. A sparse index is smaller but requires the data file to be sorted on the search key.
Dense indexes can be built on any field; sparse indexes need the data ordered on the indexed field.
Primary, clustering, and secondary indexes
A primary index is built on the ordering key field that is also a candidate key (unique). The file is sorted on it, so a sparse primary index is natural.
A clustering index is built on an ordering field that is not unique (many records share a value). It groups equal-valued records together on disk.
A secondary index is built on a non-ordering field. Because the file is not sorted on this field, a secondary index must be dense, and it usually points through an extra level of indirection.
A data file can have at most one primary or clustering index (the physical sort order), but many secondary indexes.
B-tree versus B+ tree
Both are balanced, multi-way search trees designed for disk. The difference is where data lives.
In a B-tree, keys and their record pointers sit in both internal and leaf nodes. A search can stop early at an internal node.
In a B+ tree, all actual keys and record pointers live only in the leaves; internal nodes hold only separator keys for routing. The leaves are chained in a linked list, so range queries are trivial: find the start, then walk the leaf chain.
The B+ tree wins for databases. Because internal nodes carry only keys (no record pointers), each node fits more separators, raising the fanout and lowering the tree height. Fewer levels means fewer disk reads per lookup.
Order and fanout
The order of a B+ tree bounds how many children a node may have. A node of order p holds up to p pointers and p minus 1 keys, and at least half-full by the balancing rule. Fanout is the actual number of children; high fanout is why B+ trees are wide and shallow. With fanout f and N keys, the height is about log to base f of N, and each level costs one disk read.
A worked B+ tree insert
Take a small B+ tree where each node holds at most 2 keys (it splits on the third). Insert the keys 1, 4, 7, 10, 17, 21 in order.
Insert 1, then 4: one leaf holds [1, 4].
Insert 7: the leaf would become [1, 4, 7], which overflows. Split it into [1, 4] and [7]. In a B+ tree the smallest key of the new right leaf, 7, is copied up to become the root. Root: [7], with children [1, 4] and [7].
Insert 10: 10 is at least 7, so it goes to the right leaf, giving [7, 10].
Insert 17: the right leaf would become [7, 10, 17], overflow. Split into [7, 10] and [17], and copy 17 up. Root: [7, 17], children [1, 4], [7, 10], [17].
Insert 21: 21 is at least 17, so it joins the last leaf, giving [17, 21].
The final tree has root [7, 17] and three linked leaves: [1, 4], [7, 10], [17, 21].
[DIAGRAM: The final B+ tree. A root node holding 7 and 17, with three arrows down to leaf nodes [1,4], [7,10], and [17,21]; a dashed horizontal chain links the three leaves left to right.]
Now search for 10. At the root, 10 lies between 7 and 17, so follow the middle pointer to leaf [7, 10] and find 10. That is two node accesses, the root and one leaf, so height 2. Notice every search ends at a leaf, which is what makes B+ tree lookups uniform in cost.
The disk-IO and height intuition
This uniformity is the whole point. Suppose a node fits a fanout of 100 and you have a million keys. The height is about log to base 100 of 1,000,000, which is 3. Three disk reads reach any row, against roughly a million block reads for a full scan. Increase fanout, and the height barely moves, which is why real databases keep index nodes large and half-full.
How B+ trees and indexing are tested in GATE, NET, and placements
GATE CS sets numericals: given a block size, key size, and pointer size, compute the order (maximum keys per node), the number of levels for N records, or the count of block accesses for a search or range query. B+ tree insertion with node splits and the resulting height is a repeated question type, and the B-tree-versus-B+-tree distinction shows up as a one-mark conceptual item.
UGC NET Computer Science favours the definitions: dense versus sparse, primary versus secondary, and why all keys sit in the leaves of a B+ tree. Expect direct recall rather than heavy computation.
Placement and company tests ask why a database index uses a B+ tree rather than a hash table or a binary search tree, expecting the range-query and disk-read reasoning. Knowing that leaf chaining makes range scans cheap is the answer interviewers look for.
The short version
Indexing exists to turn a disk scan into a few reads, and the B+ tree delivers it by keeping data in chained leaves and packing internal nodes with high fanout so the tree stays shallow. Draw one insert with a split until copy-up feels automatic, then reason about height from fanout. Indexing rests on the relational design you meet in SQL Queries and Joins in DBMS and Normalization in DBMS: 1NF to BCNF, so study them together. The full DBMS learn module and the GATE Guidance by Sanchit Sir course place indexing next to file organisation and query processing. Master the height intuition, and index questions become quick, reliable marks.