10. Choosing Storage Structures and Secondary Indexes : B-tree Storage Structure
 
Share this page                  
B-tree Storage Structure
B-tree is the keyed storage structure in which data is sorted by value in the key column for fast access on the exact value and range retrievals, and the index is dynamic. It is the most versatile storage structure. The B-tree structure allows for keyed access and supports range searches and pattern matching. The B-tree index is dynamic, growing as the table grows. This eliminates the overflow problems that static structures like ISAM and hash present as they grow. It is possible for a B-tree table using 2K pages to develop overflow from a leaf page with sufficient duplicate key values. B-tree secondary indexes never develop overflow because the key is always physically unique (it includes the tidp column in non-logically-unique indexes). B-tree also allows for maximum concurrent use of the table.
B-tree design incorporates a sparse index that points to pages in a leaf level. The leaf level is a dense index that points to the rows on the data pages in the table. The benefit of this indexing approach is that it minimizes splitting cost: when splitting does occur, the actual data rows need not move. Only the leaf and index levels require reorganization, as described in Index Growth in a B-tree Table.
If the configuration parameter table_auto_structure is set to ON, and if the CREATE TABLE statement includes at least a primary key, unique constraint, or referential (foreign key) constraint, the base table structure is set to B-tree on the constrained columns and the secondary index is not built.