Skip to main content

What is a B-Tree index?

SQLMiddle~1 min read
Suggest an edit

A B-Tree index is the main and most common type of index in a DBMS. It stores data in a balanced tree structure to speed up search, insertion, deletion, and sorting.

How a B-Tree is structured

  • The tree consists of nodes: a root, intermediate nodes, and leaf nodes.
  • Each node holds keys (field values) and pointers to child nodes.
  • All keys within a node are sorted, which lets it quickly find the right range.
  • Leaf nodes hold references to the actual table rows (or the data itself, when clustered).

The tree is balanced, meaning every path from root to leaf has the same length, so search always takes O(log n) steps, regardless of table size.

How a lookup works

Example: an index on age

sql
CREATE INDEX idx_users_age ON users(age);
  1. SQL starts at the root and at each level picks a direction (smaller / larger).
  2. It reaches a leaf node, which stores the exact value and a reference to the table row.
  3. For range queries (BETWEEN, >, <), it walks the leaves sequentially, since they're linked to each other.

Advantages

  • Well-suited for range lookups (>, <, BETWEEN), sorting (ORDER BY), and grouping (GROUP BY).
  • Provides logarithmic complexity (O(log n)), even with millions of rows.
  • Automatically kept balanced during inserts and deletes.

Drawbacks

  • Requires extra memory.
  • Inserts into the middle of a range are a bit slower (the tree partially rebalances).
  • Less suited to point lookups on hash values.

Summary: B-Tree is the main index type in SQL, providing fast search over sorted values. It's general-purpose and used as the default in almost every DBMS (MySQL InnoDB, PostgreSQL, Oracle, SQL Server).

Short Answer

Interview ready
Premium

A concise answer to help you respond confidently on this topic during an interview.

Suggest an edit