B-Tree Index
In one line
B-Tree indexes keep data sorted in a balanced tree — fast for lookups, ranges, and ORDER BY.
In simple words
A B-Tree (Balanced Tree) index is the most common index type. It stores key values in a balanced tree structure, keeping them sorted. This enables:
- Exact lookups — find a specific value in O(log n)
- Range queries — find values between A and B efficiently
- Sorting — ORDER BY can use the index order directly
- Prefix matching — LIKE 'abc%' can use the index
The tree is "balanced" — all leaf nodes are at the same depth, so every lookup takes the same number of steps. When data is inserted/deleted, the tree rebalances.
B-Trees are the default index type in most databases (PostgreSQL, MySQL, SQLite). They work well for columns with high cardinality (many distinct values).
Example
-- Create a B-Tree index (default in most databases)
CREATE INDEX idx_user_email ON users(email);
CREATE INDEX idx_order_date ON orders(created_at);
-- These queries use the index:
SELECT * FROM users WHERE email = '[email protected]'; -- exact lookup
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-03-31'; -- range
SELECT * FROM users ORDER BY email; -- sorting (index is pre-sorted)
SELECT * FROM users WHERE email LIKE 'ada%'; -- prefix match
-- This does NOT use the index:
SELECT * FROM users WHERE email LIKE '%example.com'; -- suffix matchB-Tree indexes speed up exact lookups, range queries, sorting, and prefix matching. They're the default index type in most databases.
Common confusions
Confused with: hash index
The difference: B-Tree indexes support exact lookups, range queries, and sorting — O(log n). Hash indexes only support exact lookups — O(1) but no ranges or sorting. B-Trees are versatile; hash indexes are faster for equality-only lookups.
Related terms
Related Resources
Related Lessons
- Database Indexes
B-Tree indexes.
Decode error messages
Plain-English explanations of common errors — what they mean, why they happen, and how to fix them.