TEST:B-Tree Indexes Deep Dive: Why Your WHERE Clause Is Fast

Complexity Analysis

All complexities below assume a B-tree of order $B$ (branching factor) with $n$ total records and tree height $h = \lceil \log_B(n) \rceil$. It is important to note that the time complexity for point lookups, $O(\log_B n)$, assumes a balanced B-tree. If the B-tree becomes unbalanced due to poor insertions or deletions, the height could approach $n$, leading to $O(n)$ complexity for lookups. This is a significant edge case that can occur in practice, especially with frequent insertions and deletions without rebalancing.

Similarly, the complexity for range scans, $O(\log_B n + k/B)$, assumes that the range scan does not require additional I/O for fetching rows. If the range is large and the data is not contiguous, it could lead to significantly more I/O operations, potentially making it worse than $O(\log_B n + k/B)$.

Operation	Time Complexity	Disk I/Os	Notes
Point lookup	$O(\log_B n)$	$h$ (typically 3-4)	One page read per tree level
Range scan ($k$ rows)	$O(\log_B n + k/B)$	$h + \lceil k/F \rceil$	$F$ = records per leaf page
Insert (no split)	$O(\log_B n)$	$h$ reads + 1 write	Traverse to leaf, append key
Insert (with split)	$O(\log_B n)$	$h$ reads + 3 writes	Split leaf + write 2 pages + update parent
Delete	$O(\log_B n)$	$h$ reads + 1 write	May trigger merge if page underfull
Index build (bulk)	$O(n \log_B n)$	$O(n/B)$	Sort-then-build avoids random I/O

The key insight is that the branching factor $B$ is large (100-500), so $\log_B(n)$ grows extremely slowly. For $n = 10^9$ and $B = 500$:

Four disk reads to find any row among a billion. With the root and first

Implementation

ALGORITHM BTreeInsert(root, key, record)
INPUT: root: page ID of the B-tree root
       key: the index key to insert
       record: the data or row pointer to store
OUTPUT: new root page ID (may change if root splits)

BEGIN
  // Phase 1: Traverse to the correct leaf
  path = empty stack
  current = BufferPool.FetchPage(root)

  WHILE current.level > 0 DO
    path.Push(current)
    child_index = BinarySearch(current.keys, key)
    current = BufferPool.FetchPage(current.children[child_index])
  END WHILE

  // Phase 2: Insert into the leaf
  InsertIntoPage(current, key, record)

  // Phase 3: Split if necessary, propagate up
  WHILE current.IsFull() DO
    median = SplitPage(current)
    IF path.IsEmpty() THEN
      // Create a new root if we are at the top level
      new_root = CreateNewRoot(median.key, current.page_id)
      RETURN new_root
    ELSE
      parent = path.Pop()
      InsertIntoPage(parent, median.key, median.new_page_id)
      current = parent
  END WHILE
END

Real-World Applications

PostgreSQL uses a variant of B-tree indexes as the default index type for all primary keys and any column with a CREATE INDEX statement. Its internal implementation has unique characteristics that differ from standard B-trees, including features that allow concurrent access without holding locks on parent nodes during splits.

MySQL/InnoDB uses a clustered index on the primary key for every table. The leaf pages of the primary key index contain the actual row data. All secondary (non-clustered) indexes store the primary key value as their row pointer instead of a physical Row ID, so a secondary index lookup requires two B-tree traversals: one on the secondary index to find the primary key, then one on the clustered index to find the row.

SQLite stores the entire database in a single file, with each table and index as a separate B-tree. Tables use B+ trees (data only in leaves), while indexes use regular B-trees. The page size defaults to 4096 bytes and can be configured at database creation.

SQL Server offers both clustered and non-clustered indexes with explicit fill factor control. The FILLFACTOR option in CREATE INDEX lets you set the percentage (1-100) of each leaf page to fill during index creation. SQL Server also supports "included columns" in non-clustered indexes, which store additional non-key columns in the leaf pages to create covering indexes that avoid bookmark lookups.

MongoDB uses B-tree indexes (specifically, WiredTiger's B-tr

Key Takeaways

• A B-tree index node is a physical disk page with a header, slot array, and cell area. The slot array enables sorted access without physically moving cells during inserts.
• Tree height determines lookup cost: with branching factors of 100-500, even billions of rows need only 3-5 disk reads. The root page is almost always cached, reducing this further.
• Page splits are the most expensive write operation. They allocate a new page, redistribute keys, and update the parent. Fill factor controls how often splits happen by leaving free space in pages.
• Clustered indexes store actual row data in the leaf pages, making range scans sequential I/O. Non-clustered indexes store key + Row ID pointers, requiring a bookmark lookup for non-covered columns.
• Fill factor is a read vs write trade-off: a high fill factor (90-100%) packs more data per page for faster reads, while a low fill factor (50-70%) leaves room for inserts to avoid splits.
• B-trees are efficient for database indexing because they handle equality, range, prefix, and ORDER BY queries effectively. They outperform hash indexes, which only support equality, and BRIN indexes, which work with naturally ordered data.