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
Merci pour vos commentaires !
Demandez à l'IA
Demandez à l'IA
Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion
Posez-moi des questions sur ce sujet
Résumer ce chapitre
Afficher des exemples du monde réel
Awesome!
Completion rate improved to 4.35B Tree
Glissez pour afficher le 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
Merci pour vos commentaires !
