B Tree Basics
What is it?
A self-balancing tree that is a generalisation of a binary search tree in that it can have more than two child nodes.
It maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time.
A B-Tree is great to use for read and write operations dealing with large amounts of data and as such is used readily with databases and file systems and normally outside of main memory.
The height of a B-Tree is kept low by keeping the maximum possible number of keys in a node of the tree.
Properties of B-Trees
- All leaves are at the same levels
- B-Tree has minimum degree
t - Every node bar root must contain
t-1keys - Root key contains minimum
1key - Children of a node equals number of keys + 1
- All nodes must contain at most
t2 - 1keys - All keys are sorted in increasing order - the child between
k1andk2must contain all keys between those values - B-Trees grow and shrink from the root
- Time complexity for search, insert and delete is
O(log(N))
Usage
B-Trees in practice are used by technologies such as MySQL, PostgreSQL, MongoDB and more.
Alternative database options with a different data structure include LSM-Trees for log structured append-only storage and is used by alternative technologies such as Cassandra, RocksDB, LevelDB, but that's another topic.
Dennis O'Keeffe
Melbourne, Australia
1,200+ PEOPLE ALREADY JOINED ❤️️
Get fresh posts + news direct to your inbox.
No spam. We only send you relevant content.
B Tree Basics
Introduction
