B-Tree in Data Structure

• B-Tree in data structure are balanced search tree design to work well on manage tic disk and other secondary storage.
• Nodes in B-tree may have many childern from a 100 to 1000 that is called the balancing factor of a b-tree
• Similar to red -black trees but shows better performance on disk input and output operations.
• Widely used in Database System

Properties of B-Tree

• B-tree is a root tree(t) having the following property:
  • Every node x has the following fields:
    • n(x) The number of keys currently stored in x (keys)
    • The n(x) keys stored in in creasing order as $key_{1}(n)\le key_{2}(n)\le …………………….\le key_{n}(n)$
    • Leaf(x) gives a Boolean value true if x is a leaf and false if x is an internal node.
• Each Internal node x also contain n(x) +1 pointers $C_{1}(x), C_{2}(x), …………………………..C_{n}(x)+1 to its childern.
• All leaf have the same depth which is called tree’s height.
• Every node other than root at least (t-1) keys thus every internal node other than root has at least (t) childern . if the tree is non-empty. The root must at least one key where $ t\ge 2 is a fixed integer called minimum degree of b-tree.
• Every node can contain at most (2t-1) this an interval node can have at most (2t) childern. A node is called full if it contain exactly (2t-1) keys.

The Height of B-Tree:

Thee number of disk access required for most operation on a b-tree is proportional to height of b-tree. So, we analyze worst tree height of b-tree if $n\ge 1$ then for any n key B-tree of height (h) and the minimum degree $ (t) \ge 2 $ the at most height .

$h \le log _{t} \frac{n+1}{2}$ where $ t \ge 2$

if a b-tree have height (n) the root contain at least one tree and all other node contain (t-1) keys . Thus , their are at least two nodes at depth 1.

Thus, the number of keys will be

$n\ge 1+ (t-1)[1+2+2t+2t^{2}………….2t^{n-1}]$

$n\ge 1 + (t-1) \sum_{i=1}^{n}2t ^{i-1}$

$n\ge 1 +2(t-1)\frac{t^{n}-1}{t-1}$

$n\ge 1 + 2t^{n}-2$

$n\ge2t^{n}-1$

$t^{n}\le n+1$

$h\le log_{t}\frac{n+1}{2}$

Why We Don’t Allow a Minimum Degree of t=1?

Because if we have minimum degree of t and it is not a root node and its parent have (t-1) keys that is 0 number of keys but we cannot have with no keys or zero keys in it. So, it violate the definition of b-tree. Thus , $t\ge 2$.

Find the maximum height of b-tree with 100,000 keys min degree = 10?

$h\le log_{t}\frac{n+1}{2}$

$h\le log_{10}\frac{100000+1}{2}$

$h\le log_{10}\frac{100001}{2}$

$ h \le 4.698 $

$ n \simeq 4 $