|1 Crore+ students have signed up on EduRev. Have you?|
Which of the following is true?
The average probability of the split is 1/([m / 2] – 1), where m is the order of B-tree. So, if m larger, the probability of split will be less.
What is the best case height of a B-tree of order n and which has k keys?
B-tree of order n and with height k has best case height h, where h = logn (k+1) – 1. The best case occurs when all the nodes are completely filled with keys.
2-3-4 trees are B-trees of order 4. They are an isometric of _____ trees.
2-3-4 trees are isometric of Red-Black trees. It means that, for every 2-3-4 tree, there exists a Red-Black tree with data elements in the same order.
Five node splitting operations occurred when an entry is inserted into a B-tree. Then how many nodes are written?
If s splits occur in a B-tree, 2s + 1 nodes are written (2 halves of each split and the parent of the last node split). So, if 5 splits occurred, then 2 * 5 + 1, i.e. 11 nodes are written.
A B-tree of order 4 and of height 3 will have a maximum of _______ keys.
A B-tree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the B-tree will have n = (mh+1 – 1) keys in this situation. So, required number of maximum keys = 43+1 – 1 = 256 – 1 = 255.
Which of the following is the most widely used external memory data structure?
In external memory, the data is transferred in form of blocks. These blocks have data valued and pointers. And B-tree can hold both the data values and pointers. So B-tree is used as an external memory data structure.
B-tree of order n is a order-n multiway tree in which each non-root node contains __________
A non-root node in a B-tree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.
A B-Tree used as an index for a large database table has 7 levels where level of the root node is 0. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are:
At every level, one new node is created except root, at two new nodes is created.
Tips and Tricks:
If database table has h levels and level of root node is 0 then on a new key insertion, maximum number of nodes newly created is h + 2
New nodes = 7 + 2 = 9
If database table has h levels and level of root node is 1 then on a new key insertion, maximum number of nodes newly created is h + 1
If a node has K children in B tree, then the node contains exactly _______ keys.
B-tree is a self-balancing search tree that allows all operations i.e. searching, insertion, deletion in logarithmic(log) time.
A B-tree of order m must satisfy the following properties:
Hence, if a node has K children in B tree, then the node contains exactly k-1 keys.
A B-Tree used as an index for a large database table has four levels including the root node. If a new key is inserted in this index, then the maximum number of nodes that could be newly created in the process are
Considering all nodes are completely full means every node has N − 1 key.
If a new key is inserted, then at every level there will be a new node created, and in the worst-case root node will also be broken into two parts. Since we have 4 levels, then 5 new nodes will be created
Diagram needs to be updated
First, the overflow happens at the leaf, and second on the parent of that leaf, and so on until the last overflow happens at the root node.
If the database table has h levels and the level of the root node is 1 then on a new key insertion, the maximum number of nodes newly created is h + 1