Published on: 24 June, 2024

Write short notes: B tree


B tree:

A B-tree is a tree structure where every node corresponds to a disk page and which satisfies the following properties:

  • A node (leaf or index) x has a value x.num as the number of objects stored in x. It also stores the list of x.num objects in increasing key order. The key and value of the i-th object (1 ≤ i ≤ x.num) are represented as x.key[i] and x.value[i], respectively.
  • Every leaf node has the same depth.
  • An index node x stores, besides x.num objects, x.num+1 child pointers. Here each child pointer is a pageID of the corresponding child node. The i th child pointer is denoted as x.child[i]. It corresponds to a key range (x.key[i − 1], x.key[i]). This means that in the i th sub-tree, any object key must be larger than x.key[i−1] and smaller than x.key[i]. For instance, in the sub-tree referenced by x.child[1], the object keys are smaller than x.key[1]. In the sub-tree referenced by x.child[2], the objects keys are between x.key[1] and x.key[2], and so on.
  • Every node except the root node has to be at least half full. That is, suppose an index node can hold up to 2B child pointers (besides, of course, 2B-1 objects), then any index node except the root must have at least B child pointers. A leaf node can hold more objects, since no child pointer needs to be stored. However, for simplicity we assume a leaf node holds between B and 2B objects.
  • If the root node is an index node, it must have at least two children.

A special case of the B-tree is when B = 2. Here every index node must have 2 or 3 or 4 child pointers. This special case is called the 2-3-4 tree. Figure 15.1 shows an example of a B-tree. In particular, it’s a 2-3-4 tree.

In the figure, every index node contains between 2 and 4 child pointers, and every leaf node contains between 2 and 4 objects. The root node A is an index node. Currently it has one object with key=25 and two child pointers. In the left sub-tree, every object has key25. Every leaf node (D through I) are located at the same depth: their distance to A is 2. Currently, there are two pages which are full: an index node B and a leaf node D.

Random questions