DBMS: Balanced Tree (Definitions)

"Short for balanced tree, or binary tree. SQL Server uses B-tree indexing. All leaf pages in a B-tree are the same distance from the root page of the index. B-trees provide consistent and predictable performance, good sequential and random record retrieval, and a flat tree structure." (Karen Paulsell et al, "Sybase SQL Server: Performance and Tuning Guide", 1996)

"A data structure that resembles a tree, it is also called a balanced tree." (Owen Williams, "MCSE TestPrep: SQL Server 6.5 Design and Implementation", 1998)

"This term describes SQL Server index structures." (Microsoft Corporation, "SQL Server 7.0 System Administration Training Kit", 1999)

"A relational index that is particularly useful for high-cardinality columns. The B-tree index builds a tree of values with a list of row IDs that have the leaf value. B-tree indexes are almost worthless for low-cardinality columns because they take a lot of space and they usually cannot be combined with other indexes at the same time to increase the focus of the constraints. Contrast with Bitmap index." (Ralph Kimball & Margy Ross, "The Data Warehouse Toolkit" 2nd Ed, 2002)

"A structure for storing index keys; an ordered, hierarchical, paged assortment of index keys. Some people say the 'B' stands for 'Balanced'." (Peter Gulutzan & Trudy Pelzer, "SQL Performance Tuning", 2002)

"A type of index structure that resembles an inverted tree. The branches of a b-tree index are balanced. Traversing the tree for any index value reads the same number of blocks." (Bob Bryla, "Oracle Database Foundations", 2004)

"Short for binary-tree , this is the structure of an index in SQL Server. It’s called this because it resembles a tree when drawn. Starting with a root page, it expands into leaf pages where data is stored." (Joseph L Jorden & Dandy Weyn, "MCTS Microsoft SQL Server 2005: Implementation and Maintenance Study Guide - Exam 70-431", 2006)

"An abstract data type used to store indexes in SQL Server." (Marilyn Miller-White et al, "MCITP Administrator: Microsoft SQL Server 2005 Optimization and Maintenance 70-444", 2007)

"A self-balancing tree data structure that allows efficient searching of indexes. A b-tree stores data records in internal and leaf nodes." (Rod Stephens, "Beginning Database Design Solutions", 2008)

"A data structure commonly used by database management systems to store indexes. MongoDB uses B-trees for its indexes." (MongoDb, "Glossary", 2008)

"A keyed, treelike index structure." (Craig S Mullins, "Database Administration", 2012)

"A tree structure for storing database indexes." (Microsoft, "|SQL Server 2012 Glossary", 2012)

"An index organized like an upside-down tree. A B-tree index has two types of blocks: branch blocks for searching and leaf blocks that store values. The leaf blocks contain every indexed data value and a corresponding rowid used to locate the actual row. The 'B' stands for 'balanced' because all leaf blocks automatically stay at the same depth." (Oracle, "Database SQL Tuning Guide Glossary", 2013)

"An index that is arranged as a balanced hierarchy of pages and that minimizes access time by realigning data keys as items are inserted or deleted." (Sybase, "Open Server Server-Library/C Reference Manual", 2019)

"A hierarchical indexing technique based on an inverted tree of nodes containing ranges of indexed values. Going down the hierarchical levels, the nodes progressively contain smaller numbers of index values, so that any value may be searched for in a few trials by starting at the top." (Paulraj Ponniah, "Data Warehousing Fundamentals for IT Professionals", 2010)