B-tree
Sign in to saveIn computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing nodes to have more than two children.
Key facts
- Data structure amortized.name
- B-tree
- Data structure amortized.type
- Tree (data structure)
- Data structure amortized.invented_by
- Rudolf Bayer, Edward M. McCreight
- Data structure amortized.invented_year
- 1970
- Data structure amortized.space_avg
- O(n)
- Data structure amortized.search_avg
- O(\log n)
- Data structure amortized.search_worst
- O(\log n)
- Data structure amortized.insert_avg
- O(\log n)
- Data structure amortized.insert_worst
- O(\log n)
- Data structure amortized.delete_avg
- O(\log n)
- Data structure amortized.delete_worst
- O(\log n)
via Wikipedia infobox
Article
36 sectionsContents
- History
- Definition
- Differences in terminology
- Informal description
- Node structure
- Insertion and deletion
- Comparison to other trees
- Variants
- B-tree usage in databases
- Sorted file search time
- Index performance
- Insertions and deletions
- Usage in databases
- Best case and worst case heights
- Algorithms
- Search
- Insertion
- Deletion
- Deletion from a leaf node
- Deletion from an internal node
- Rebalancing after deletion
- Sequential access
- Initial construction
- In filesystems
- Performance
- Variations
- Access concurrency
- Parallel algorithms
- Maple tree
- (a,b)-tree
- See also
- Notes
- References
- Sources
- Original papers
- External links
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing nodes to have more than two children.
By allowing more children under one node than a regular self-balancing binary search tree, the B-tree reduces the height of the tree and puts the data in fewer separate blocks. This is especially important for trees stored in secondary storage (e.g., disk drives), as these systems have relatively high latency and work with relatively large blocks of data, hence the B-tree's use in databases and file systems. This remains a major advantage when the tree is stored in memory, as modern computer systems rely heavily on CPU caches. Compared to reading from the cache, reading from memory after a cache miss costs significant time.