B-tree
E97112
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
Aliases (3)
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
data structure
→
self-balancing search tree → tree data structure → |
| advantage |
good cache performance
→
reduces disk I/O operations → |
| comparedTo |
binary search tree
→
|
| constraint |
all leaves appear on the same level
→
each node (except root) has a minimum number of keys → each node has a maximum number of keys → keys in a node separate key ranges of children → root has at least two children unless it is a leaf → |
| describedIn |
"Organization and Maintenance of Large Ordered Indexes"
→
|
| differenceFromBinarySearchTree |
designed for external memory
→
nodes can have more than two children → |
| field |
computer science
→
|
| generalizationOf |
binary search tree
→
|
| hasVariant |
B# tree
→
B* tree → B+ tree → |
| introducedBy |
Edward M. McCreight
→
Rudolf Bayer NERFINISHED → |
| introducedIn |
1972
→
|
| nodeContains |
multiple keys
→
pointers to child nodes → |
| optimizedFor |
block-oriented storage
→
disk access efficiency → |
| property |
all leaves at same depth
→
balanced height → height grows logarithmically with number of keys → keys stored in sorted order → multi-way branching → nodes can have many children → |
| supportsOperation |
delete
→
insert → range queries → search → sequential traversal → |
| timeComplexityDeletion |
O(log n)
→
|
| timeComplexityInsertion |
O(log n)
→
|
| timeComplexitySearch |
O(log n)
→
|
| typicalApplication |
file systems
→
key-value stores → relational database systems → |
| usedFor |
database indexing
→
efficient deletion → efficient insertion → efficient search → file system indexing → storing sorted data → |
Referenced by (4)
| Subject (surface form when different) | Predicate |
|---|---|
|
B-tree
("B+ tree")
→
B-tree ("B# tree") → |
hasVariant |
|
B-tree
(""Organization and Maintenance of Large Ordered Indexes"")
→
|
describedIn |
|
PostgreSQL
→
|
supportsIndexType |