MindStudy - MindStudy

Question:

Published on: 19 April, 2024

Write short notes: B tree

Answer:

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.

Subjects

Mobile computing Computer Graphics and Multimedia C Programming and Practices Data Structures & Algorithm Software Engineering Compiler Design

Trending

What do you mean by ‘Ternary Relationship’? Define the concept of aggregation with suitable example.

19 April, 2024

Let R (ABCDE) be a relation schema and consider the following functional dependencies

F = { AB→ E, AD→B, B→ C, C→D}.

Find out the candidate key.

23 January, 2022

Explain two-phase locking protocol.