B+ Tree Index
Balanced tree data structure for database indexing
A B+ Tree index is a balanced, sorted tree data structure used by most relational databases to enable fast lookups, range scans, and ordered traversal of indexed columns.
Definition
A B+ Tree index is a balanced, sorted tree data structure used by most relational databases to enable fast lookups, range scans, and ordered traversal of indexed columns.
Overview
A B+ Tree is a variant of the B-tree data structure, adapted specifically for the way databases read and write data in fixed-size disk pages. Like a standard B-tree, it stays balanced as data is inserted and deleted, keeping all leaf nodes at the same depth so that any lookup takes a predictable, small number of page reads regardless of how large the table grows. Its key difference from a plain B-tree is that all actual data references live only in the leaf nodes, while internal nodes hold only routing keys used to navigate down to the correct leaf; the leaf nodes are also linked together in sorted order, forming an efficient path for range scans and ordered traversal. This structure is what makes B+ Trees the default index type in nearly every relational database — PostgreSQL, MySQL's InnoDB, SQLite, and Oracle all use B+ Trees as their primary index structure. A query like `WHERE age > 30` can walk down to the first leaf matching `age = 30` and then simply follow the linked leaf nodes forward, reading a contiguous sorted range without needing to re-traverse the tree for every row, which is far more efficient than the equivalent operation would be on a hash index, which offers fast equality lookups but no ordering. Each node in a B+ Tree typically holds many keys — often hundreds — sized to fill a single disk page, which keeps the tree's height very small even for tables with millions of rows; a table with a billion rows might still only require three or four page reads to find any given entry. Insertions and deletions maintain this balance automatically by splitting overfull nodes or merging underfull ones, which is what keeps lookup performance consistent as data changes over time. Databases also support other index types for different access patterns — hash indexes for pure equality lookups, and specialized structures like GiST, GIN, or inverted indexes for full-text search and complex data types — but B+ Trees remain the default general-purpose choice because they handle both equality and range queries well.
Key Concepts
- Balanced tree structure with all leaf nodes at equal depth
- Leaf nodes linked together in sorted order for efficient range scans
- Internal nodes hold routing keys only, not data references
- Default index structure in PostgreSQL, MySQL InnoDB, SQLite, and Oracle
- Node size tuned to disk page size, minimizing tree height and page reads
- Automatically rebalances via node splits and merges on insert or delete
- Supports both equality lookups and ordered range queries efficiently
Use Cases
Frequently Asked Questions
From the Blog
What Is a Decision Tree in Machine Learning
A decision tree predicts by asking a series of yes/no questions about your data, splitting it step by step until it reaches an answer. It is simple, visual, and easy to read.
Read More AI & TechnologyHNSW, IVF and Flat: How to Pick a Vector Index
Flat gives exact results and scans everything, IVF partitions the space and searches a few partitions, and HNSW navigates a layered proximity graph. This article compares them on build time, memory, recall and update cost, and gives a decision path by corpus size.
Read More AI & TechnologyHow to Keep a RAG Index Fresh as Documents Change
Keep a RAG index fresh by detecting change at the source, upserting only affected chunks with stable identifiers, and propagating deletions as first-class events. This covers change detection, deterministic chunk IDs, tombstoning, reindex triggers and the monitoring that tells you when stale content is still being served.
Read More AI & TechnologyHow to Migrate a Vector Index Without Downtime
Migrate a vector index by writing to both the old and new index for a period, shadow-reading the new one to compare results, then cutting reads over behind a flag with the old index still warm. This keeps queries serving throughout and makes rollback a configuration change rather than a rebuild.
Read More