Advantages of B-Tree in DBMS
A self-balancing search tree is the B-Tree. It is assumed that everything is in the main memory in most other self-balancing search trees (such as AVL and Red-Black Trees).
We must consider the vast amount of data that won't fit in the main memory to comprehend the utilization of B-Trees. Data is read from the disc in blocks when the number of keys is high. Disc access time is very long compared to the access time to main memory. Reducing the amount of disc accesses is the primary goal of employing B-Trees. Most tree operations, such as search, insert, delete, max, min, etc., call for O(h) disc accesses, where h is the tree height. By packing as many keys as you can into each B-Tree node, the size of B-Trees is maintained to a minimum.
Example
Assume that one disc read operation is required to reach one B tree node. A B-tree of order 101 and height three may hold 100 million items.
With a maximum of three disc reads, any item can be accessible.
Since all the leaves are at the same level, a B tree is also known as a multi-way search tree and is a type of multilevel indexing.
The root of a tree grows, not the leaf.
B-tree properties
A B-tree satisfies the following properties –
- A node (not a leaf node) has one less number of keys than its children (these keys split the children's keys like a binary search tree).
- A trunk has at least one key, up to a maximum of (m-1) keys. So the root has at least two up to m children.
- A node has as many children as its number of keys plus one.
- In contrast to Binary Search Tree, the B-Tree expands and contracts from the root. Binary Search Trees shrink as well as grow downhill.
Note: Non-leaf nodes are called internal nodes (nodes with children). Leaf nodes are called external nodes (nodes that have no children).
Example
A B-tree of degree 3 (i.e., a node can have up to 3 children) satisfies the following properties –
- A root has at least one and, at most, two keys. Therefore, the heart has at least two and at most three children.
- 5 Each non-root node (not leaf node) has at least one and at most two keys. So there are at least two children and a maximum of 3 children.
Note: Duplicate strong values are not allowed.
Advantages of B-Tree
B-trees use all the above ideas. Specifically, the B-tree:
- The B-Tree works well compared to a hash table since it enables ordered sequential access.
- Similar to how a binary tree supports it, it allows iterations over objects. If necessary, the things are arranged via iterations in the appropriate order (ascending or descending).
- Millions of objects can be kept in the tree, and its flat form makes it simple and quick to navigate the data.
- The cost of deleting a record from a table when millions of records can add up since the table may need to be rewritten. However, if the complete data set is used or B-Tree is utilized to handle sequential access to the table.
- Use hierarchical indexes to minimize disk reads.
- Use partially complete blocks to speed up inserts and deletes.
- Use a recursive algorithm to keep the index balanced.
- Additionally, B-trees minimize waste by ensuring interior nodes are at least half full.
- A B-tree can handle any number of insertions and deletions.
- BST accesses fewer memory locations during a search than B-tree, but these accesses are more expensive because each access is more likely to cause a cache miss.
- B-trees go to more locations overall, but these accesses are less expensive because there are fewer cache misses.
- Recordings can be recalled with the same number of disk accesses.
- The tree's height remains balanced and is lower than the B tree.
- Data stored in a B+ tree can be accessed sequentially and directly.
- Keys are used for indexing.
- Searches are faster because data is stored only in leaf nodes.
- The cost of accessing the disc is high while querying tables on a computer, yet the amount of data transferred is unimportant. Therefore, minimizing disc access is our goal.
- We are aware that we cannot increase a tree's height. Therefore, we want the tree to be as short as possible.
- Using a B-tree, which has more branches and hence a shorter height, is the solution to this problem. Access time decreases as branching and depth grow.