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

Все було зрозуміло?

Секція 4. Розділ 2