# Indexes: B+ Trees and Hashing — Database Fundamentals

Source: https://www.skillbyai.com/en/database-fundamentals/s-index

> Explain how B+ tree and hash indexes work and when each is used.

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

```sql
-- 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.

**Quiz:** 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
- [x] Their leaf nodes are sorted and linked, so the range can be scanned sequentially after one search

*Answer:* Their leaf nodes are sorted and linked, so the range can be scanned sequentially after one search. One descent finds the start of the range; linked leaves then deliver the rest in order.