**B-tree**(Balanced Tree Index) is a self-balancing tree data structure. The B-tree is a generalization of a binary search and it is optimized by systems in-order to keep logarithmic time.

## 🐞 B-tree usage in database

In B-trees, internal (non-leaf) nodes can have a variable number of child nodes within some pre-defined range. When data is inserted or removed from a node, its number of child nodes changes. In order to maintain the pre-defined range, internal nodes may be joined or split. Because a range of child nodes is permitted, B-trees do not need re-balancing as frequently as other self-balancing search trees but may waste some space, since nodes are not entirely full.

Each internal node of a B-tree contains a number of keys. The keys act as separation values which divide its subtrees. For example, if an internal node has 3 child nodes(or subtrees) then it must have 2 keys:

`a1`

and`a2`

. All values in the leftmost subtree will be less than`a1`

, all values in the middle subtree will be between`a1`

and`a2`

, and all values in the rightmost subtree will be greater than`a2`

.

Usually, sorting and searching algorithms have been characterized by the number of comparison operations that must be performed using order notation. A binary search of a sorted table with N records, for example, can be done in roughly

`o(log N)`

. If the table had 1,000,000 records, then a specific record could be located with at most 20 comparisons:`log (1,000,000) = 20`

.

There are some advantages of B-tree usage for a database. A B-tree:

- keeps keys in sorted order for sequential traversing
- uses a hierarchical index to minimize the number of disk reads
- uses partially full blocks to speed insertions and deletions
- keeps the index balanced with a recursive algorithm

In addition, a B-tree minimizes waste by making sure the interior nodes are at least half full. A B-tree can handle an arbitrary number of insertions and deletions.

https://en.wikipedia.org/wiki/B-tree

## 🖥 Recommended VPS Service

**VULTR** provides high performance cloud compute environment for you.
Vultr has 15 data-centers strategically placed around the globe, you can use a VPS with 512 MB memory for just $ 2.5 / month ($ 0.004 / hour).
In addition, Vultr is up to 4 times faster than the competition, so please check it => **Check Benchmark Results**!!