ByteNotesByteNotesByteNotes

Indexing

Without an index, a database must scan every row in a table to find matches — an O(n) full table scan. An index pre-sorts a subset of the data so the engine can jump directly to relevant rows. The trade-off is always the same: indexes speed up reads but slow down writes (every insert and update must maintain the index) and consume additional storage.

How Indexes Work

An index is a separate data structure that the database maintains in parallel with the table. It stores a subset of the columns in a form optimised for lookup, along with a pointer (row ID or primary key) back to the full row. When the query planner sees a predicate that matches an index, it uses the index to find the row pointers and fetches only those rows — instead of reading the entire table.

Index selectivity

Selectivity measures how many distinct values an index column has relative to the total number of rows. A highly selective index (e.g. user_id on a users table) narrows the result set dramatically and is worth using. A low-selectivity index (e.g. is_active on a table that is 95% active) returns so many rows that the planner often prefers a sequential scan instead.

Clustered vs non-clustered

  1. Clustered index — the table rows are physically stored in index order. There can only be one per table (MySQL InnoDB clusters on the primary key by default). Range scans are extremely fast because the rows are contiguous on disk.
  2. Non-clustered index — a separate structure that holds the indexed values and pointers back to the heap (the unsorted table). Multiple non-clustered indexes can exist on a single table. Each pointer lookup may cause a random read ("heap fetch"), which adds I/O cost.

B-Tree Index

The default index type in PostgreSQL, MySQL, SQLite, and most SQL databases. A self-balancing tree keeps all leaf nodes at the same depth, guaranteeing O(log n) lookups, inserts, and deletes regardless of data distribution.

Structure

  1. Internal nodes store separator keys and pointers to child nodes, guiding the search down the tree.
  2. Leaf nodes hold the actual indexed values and row pointers. In a B+Tree variant (used by most databases), leaf nodes are also linked in a doubly-linked list so range scans can walk the leaves sequentially without returning to the root.

Supported operations

  1. Exact lookup: WHERE id = 42
  2. Range scan: WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'
  3. Prefix match: WHERE name LIKE 'Jo%'
  4. Ordering: ORDER BY indexed_column can use the leaf-node list without a separate sort step
  5. Min / Max: the leftmost or rightmost leaf is read directly — O(log n)

What B-Trees cannot do

B-Trees sort values lexicographically (or numerically). They do not support suffix matching (LIKE '%smith'), arbitrary function predicates (WHERE lower(email) = … without a functional index), or multi-dimensional spatial queries — those require specialised index types like GIN, GiST, or an R-Tree.

Hash Index

A hash index applies a hash function to the indexed column value and stores entries in a hash table. Lookups are O(1) average for exact-match queries — faster than B-Tree's O(log n). However, hash indexes have significant limitations:

  1. No range queries — hashing destroys order; WHERE age > 30cannot use a hash index.
  2. No ordering — ORDER BY cannot benefit from a hash index.
  3. No prefix matching — partial string matches are not supported.
  4. Hash collisions — many values hashing to the same bucket degrade performance toward O(n) in the worst case.

In PostgreSQL, hash indexes are durable and WAL-logged since version 10. In MySQL InnoDB, hash indexes are maintained automatically by the engine as an adaptive structure — you cannot create one manually. In practice, B-Tree covers most use cases and hash indexes are rarely chosen explicitly.

Composite Indexes

A composite (multi-column) index orders rows by the first column, then by the second within ties, and so on. This has two important consequences:

The leftmost-prefix rule

An index on (user_id, created_at) can be used by queries that filter on:

  • WHERE user_id = 5 — uses the first column only
  • WHERE user_id = 5 AND created_at > '2024-01-01' — uses both columns

But it cannot be used by:

  • WHERE created_at > '2024-01-01' — skips the leading column

Design composite indexes around your most frequent query patterns, leading with the most selective and most commonly filtered column.

Column order for range vs equality

Put equality predicates before range predicates. An index on (status, created_at) serves WHERE status = 'active' AND created_at > …well — the engine jumps to the status = 'active' section of the index and then scans the ordered created_at range. Reversing the order to (created_at, status) would force a range scan on created_at first, then filter status in memory.

Covering Indexes

A covering index includes all columns a query needs — both the filter columns and the select columns — so the database never has to touch the base table at all. This eliminates the heap fetch entirely.

For a query like:

SELECT email FROM users WHERE user_id = 42

An index on (user_id, email) is covering: the engine finds user_id = 42 in the index and reads email directly from the index leaf — zero table I/O.

PostgreSQL supports this via INCLUDE columns (non-key columns stored in leaf nodes but not used for ordering). MySQL InnoDB achieves the same effect because secondary indexes already include the primary key.

Fractional Indexing

Fractional indexing is an ordering strategy — not a database index type — for maintaining a user-defined sort order in a list without renumbering every row on every move. It is the technique behind drag-and-drop reordering in collaborative tools like Figma, Notion, and Linear.

The problem with integer positions

The naïve approach is to store an integer position column and shift all subsequent rows when an item moves. Moving item 3 to position 1 requires updating every row with position >= 1 — an O(n) write that causes conflicts in multi-user environments and locks the table.

How fractional indexing works

Instead of integers, each item is assigned a decimal or string key that sorts between its neighbours. To insert or move an item between two existing items, pick a value strictly between their keys — no other rows need to change.

  1. Items A, B, C are assigned keys 1.0, 2.0, 3.0.
  2. Moving D between A and B: assign (1.0 + 2.0) / 2 = 1.5. Only D's row is written.
  3. Moving E between A and D: assign (1.0 + 1.5) / 2 = 1.25. Again, one write.

Precision exhaustion

Repeatedly bisecting the same gap produces keys with ever-increasing decimal places: 1.5 → 1.25 → 1.125 → 1.0625 … After enough operations, floating-point precision runs out and keys collide. Two mitigations:

  1. String keys — use lexicographically sortable strings (e.g. "a0", "a1", "a0V"). The key space grows by appending characters rather than adding decimal places, so the space is effectively unbounded. Libraries like fractional-indexing (npm) implement this.
  2. Periodic rebalancing — when keys grow beyond a threshold length, reassign evenly spaced keys to all items in the list in a background job. This is a rare, batched O(n) write rather than a per-operation cost.

Storing and querying

The key is stored in a plain indexed column (TEXT or FLOAT). Fetching a list in order is a simple ORDER BY position_key — the B-Tree index on that column makes it O(log n + k) where k is the result size. Because moves only update one row, write contention in collaborative scenarios is minimal.

When to use it

  1. User-defined ordering of lists, cards, or tasks (Kanban boards, to-do apps).
  2. Collaborative editors where multiple users may reorder items concurrently.
  3. Any list where the order changes frequently and O(n) position shifts are unacceptable.

When Not to Index

  1. Low-cardinality columns — boolean flags, status enums with few values. The index is not selective enough; the planner often ignores it and scans the table instead.
  2. Write-heavy tables — every insert, update, or delete must maintain all indexes on the table. A table with ten indexes pays ten write penalties per row change. Profile first; index only what queries actually need.
  3. Small tables — if the table fits in a handful of data pages, a sequential scan is faster than an index lookup because it avoids the random I/O of following row pointers.
  4. Columns never used in predicates or joins — an index that no query ever uses wastes storage and write bandwidth with no benefit.
  5. Highly correlated columns — if column_b is always derivable from column_a, indexing both separately adds cost without additional selectivity.