Indexes: B+ Trees and Hashing

Finding rows without scanning

An index is an auxiliary structure that maps key values to record locations. The workhorse is the B+ tree: a balanced tree whose internal nodes hold keys that guide the search and whose leaf nodes hold the keys with record pointers (or the rows themselves), linked to each other in key order. Because each node holds hundreds of keys (high fan-out), even billions of rows need only three or four levels, so lookups take a few page reads, and the linked leaves make range queries and ORDER BY efficient. Inserts and deletes keep the tree balanced by splitting and merging nodes. Hash indexes apply a hash function to the key and are fast for equality lookups but useless for ranges. A clustered (primary) index stores rows in index order (InnoDB tables are clustered on the primary key); a non-clustered (secondary) index points to rows stored elsewhere. Composite indexes on several columns follow the leftmost-prefix rule, and a covering index contains every column a query needs. Indexes speed reads but slow writes and use space, so create them for real query patterns.

Indexes for real queries

Each index is designed for a specific access pattern.

-- equality on one column
CREATE INDEX idx_students_email ON students (email);

-- composite index: supports (dept), (dept, year), (dept, year, score)
-- but not (year) alone or (score) alone - leftmost prefix rule
CREATE INDEX idx_marks_dept_year_score ON results (dept, year, score);

SELECT * FROM results WHERE dept = 'CSE' AND year = 2026 ORDER BY score DESC;   -- uses it
SELECT * FROM results WHERE year = 2026;                                         -- cannot use it efficiently

-- covering index: the query never touches the table rows
CREATE INDEX idx_orders_cust_date ON orders (customer_id, order_date) INCLUDE (total);  -- PostgreSQL syntax
SELECT order_date, total FROM orders WHERE customer_id = 42;

The index at the back of a textbook

Instead of reading every page to find "deadlock", you look it up in the sorted index and jump to page 214. A composite index is like an index sorted by chapter and then by term: easy to search within a chapter, useless if you only know the term.

त्वरित जाँच: Why are B+ trees well suited to range queries such as `score BETWEEN 80 AND 90`?

• They hash every key
• They store only one key per node
• They avoid using disk
• Their leaf nodes are sorted and linked, so the range can be scanned sequentially after one search