MindStudy - MindStudy

Question:

Published on: 22 December, 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

C Programming and Practices Compiler Design Software Engineering Mobile computing Design and Analysis of Algorithm Data Structures & Algorithm

Trending

What is the need for normalization? Explain 2nd and 3rd normal form with example.

Consider the following relation:

EMP_PROJ { SSn, Pnumber, Hours, Ename, Pname, Plocation}

Assume { SSn, Pnumber} as primary key.

The dependencies are {SSn, Pnumber}→ Hours; SSn →Ename; Pnumber → {Pname, Plocation}.

Normalize the above relation into 2NF.

23 January, 2022

Consider the relation R={A,B,C,D,E,F,G,H,I,J} and the set of functional dependencies: F={AB → C, A → DE, B → F, F → GH, D → IJ}. Decompose R into 3NF.

22 December, 2024

Explain two-phase locking protocol.

22 December, 2024

What are the differences between Primary Index, Secondary Index, and Clustering Index?

22 December, 2024

Write short notes on the following: