Skip to content

B+ tree index structure

The B+ tree index structure is the data organization format used by storage engines like InnoDB to optimize data retrieval and storage operations.^[600-developer__mysql.md]

Structure and Capacity

A B+ tree is a balanced tree structure where data is stored in both index pages (internal nodes) and data pages (leaf nodes).^[600-developer__mysql.md] In the InnoDB storage engine, the standard size for these pages is typically 16 KB.^[600-developer__mysql.md] This structure is highly efficient, allowing a B+ tree with a height of only 3 levels to store data in the millions.^[600-developer__mysql.md]

The leaf nodes of the B+ tree are organized as a doubly linked list, enabling efficient sequential scanning of data.^[600-developer__mysql.md] The internal nodes effectively form a "directory" that points to the actual "data," separating the index structure from the data storage itself.^[600-developer__mysql.md]

Functionality

Primary Keys and Insertion

When using the B+ tree structure for a primary key, data insertion requires sorting the data before it is placed into the tree.^[600-developer__mysql.md]

Range Queries

The B+ tree structure is specifically designed to support range searches effectively.^[600-developer__mysql.md] This capability allows the database to efficiently satisfy queries that look for values within a specific interval.

Retrieval Methods

The structure supports specific query patterns, including: * Index Scan: Traversing the tree structure. * Covering Index: A scenario where all required columns are present within the index itself, avoiding the need to access the main data table (also known as "returning to the table" or "hui biao").^[600-developer__mysql.md]

Usage Considerations

Operations on Columns

Queries that perform operations on indexed columns may lead to index failure.^[600-developer__mysql.md] For example, a query condition like WHERE a + 1 = 5 cannot use the index on column a.^[600-developer__mysql.md]

Composite Indexes

When using composite indexes (indexes on multiple columns), the "Leftmost Prefix" principle must be observed to utilize the index effectively.^[600-developer__mysql.md] Additionally, the columns in the composite index must typically be of the same type to function as expected.^[600-developer__mysql.md]

Sources

  • 600-developer__mysql.md