B Tree
| Operation | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Memory Complexity |
|---|---|---|---|---|
Search | O(log n) | O(log n) | O(log n) | O(n) |
Insertion | O(log n) | O(log n) | O(log n) | O(n) |
Deletion | O(log n) | O(log n) | O(log n) | O(n) |
Letβs talk briefly about the first non-binary tree - B-tree.
When building a B-tree, a factor t is used, which is called the minimum degree. The value of t depends upon disk block size. Each node except the root must have at least t - 1 and no more than 2t - 1 keys. n[x] - the number of keys in node x.
The keys in a node are stored in non-decreasing order. If x is not a leaf, then it has n[x] + 1 children. The keys of a node define a range for the keys of their children.
All leaves of a B-tree must be located at the same height, which is the height of the tree.
We can perform the same operations with the B-tree as we performed with BST: searching, insertion, deletion.
B-trees are also balanced trees, so the time to perform standard operations in them is proportional to the height. But, unlike other trees, they are designed specifically to work efficiently with disk memory, or rather, they minimize I / O type calls.
There are some more B-tree type trees:
- B* tree
- BβΊ tree
They differ a little bit but in general they have the same structure.
You can study them on your own.
Thatβs all for now!
Letβs take a quiz!
An example of the B-tree with t = 3
Thanks for your feedback!
Ask AI
Ask AI
Ask anything or try one of the suggested questions to begin our chat
Ask me questions about this topic
Summarize this chapter
Show real-world examples
Awesome!
Completion rate improved to 4.35B Tree
Swipe to show menu
| Operation | Best Time Complexity | Average Time Complexity | Worst Time Complexity | Memory Complexity |
|---|---|---|---|---|
Search | O(log n) | O(log n) | O(log n) | O(n) |
Insertion | O(log n) | O(log n) | O(log n) | O(n) |
Deletion | O(log n) | O(log n) | O(log n) | O(n) |
Letβs talk briefly about the first non-binary tree - B-tree.
When building a B-tree, a factor t is used, which is called the minimum degree. The value of t depends upon disk block size. Each node except the root must have at least t - 1 and no more than 2t - 1 keys. n[x] - the number of keys in node x.
The keys in a node are stored in non-decreasing order. If x is not a leaf, then it has n[x] + 1 children. The keys of a node define a range for the keys of their children.
All leaves of a B-tree must be located at the same height, which is the height of the tree.
We can perform the same operations with the B-tree as we performed with BST: searching, insertion, deletion.
B-trees are also balanced trees, so the time to perform standard operations in them is proportional to the height. But, unlike other trees, they are designed specifically to work efficiently with disk memory, or rather, they minimize I / O type calls.
There are some more B-tree type trees:
- B* tree
- BβΊ tree
They differ a little bit but in general they have the same structure.
You can study them on your own.
Thatβs all for now!
Letβs take a quiz!
An example of the B-tree with t = 3
Thanks for your feedback!
