B Tree Basics
April 19, 2019
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
- Every node bar root must contain
- Root key contains minimum
- 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
k2must contain all keys between those values
- B-Trees grow and shrink from the root
- Time complexity for search, insert and delete is
B-Trees in practice are used by technologies such as
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
LevelDB, but that’s another topic.
A personal blog on all things of interest. Written by Dennis O'Keeffe, Follow me on Twitter