Part 4 of 5 · 2 min read
The two parts of a typical index: search tree and leaf nodes
A search tree narrows down to the right leaf node, which holds the actual matching entries.
The two parts of a typical index: search tree and leaf nodes
Think of the library catalog again, but as a set of signs. A sign for "A-M" and one for "N-Z" each point to a narrower sign, and so on, until the last sign points to the actual drawer of cards.
In plain words: most index structures, including the B+-trees covered in depth on the next page, are organized as a search tree sitting above a set of leaf nodes. The search tree holds no actual data. It exists purely to narrow down, level by level, which leaf node holds the entries for a given search value. The leaf nodes hold the real entries: the indexed value, and a pointer to the matching row or rows.
A worked example. Searching an index on customer_id for the value 42 walks down a few levels of the search tree, each level narrowing the range, until it reaches one leaf node holding the actual entry for customer_id = 42 and a pointer to its row.
The key lines. No new SQL; the search-tree-and-leaves structure is internal to how the database executes the earlier CREATE INDEX example.
Search tree, leaf node
An index's search tree is the set of internal levels used purely to narrow down which leaf node holds the actual entries; a leaf node stores the indexed values themselves along with pointers to their matching rows.
Example: the catalog's "A-M" and "N-Z" signs are the search tree; the actual drawer of cards they point to is a leaf node.
Remember this
An index turns "read every row" into "walk a few levels of a tree, then read only the matching rows." The next page covers exactly how that tree, the B+-tree, is built and kept balanced.
Quick notes
- With no index, a query must perform a full table scan: read and check every row.
- An index is a separate structure mapping column values to row locations, at the cost of extra storage and write maintenance.
- A typical index has a search tree, which narrows down which leaf node to check, and leaf nodes, which hold the real entries.
- An index only helps queries that filter on the indexed column; a filter on a different, unindexed column still needs a full scan.