Home › Reference › Glossary › B-tree

B-tree

The sorted tree most databases use for an index. A lookup walks a few levels, and the tree gains a level only when the table grows by hundreds of times.

Taught in Chapter 19: Indexes.

More from the same chapter

• Bloom filter: A small bit array that says a key is definitely not in a set, or maybe is. A maybe is sometimes wrong; a no is right every time.
• Compaction: An LSM tree's background merge of its sorted files, which drops overwritten and deleted values.
• Covering index: An index that holds every column a query needs, so the database answers it without reading the table.
• Geohash: A latitude and longitude encoded as a string in which nearby points mostly share a prefix, so a cell can be found with an ordinary index.
• Index: A sorted lookup structure beside a table, so the database finds rows without scanning them all.
• Inverted index: For every word, the list of documents that contain it. What full-text search reads instead of scanning.
• LSM tree: A store that writes to memory and appends sorted files, merging them in the background. Cheap writes, reads that may check several files.
• Quadtree: A map split into four, and the busy parts split again, so a dense city gets small cells and an ocean one large one.
• Query planner: The part of a database that chooses how to run a search, such as a table scan or an index, from statistics about the data.
• Selectivity: The share of a table's rows a search returns. The smaller the share, the more an index is worth having.
• Table scan: Answering a query by reading every row of a table, at a cost that grows with its size.