1 Crore+ students have signed up on EduRev. Have you? 
The average probability of the split is 1/([m / 2] – 1), where m is the order of Btree. So, if m larger, the probability of split will be less.
What is the best case height of a Btree of order n and which has k keys?
Btree 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.
234 trees are Btrees of order 4. They are an isometric of _____ trees.
234 trees are isometric of RedBlack trees. It means that, for every 234 tree, there exists a RedBlack tree with data elements in the same order.
Five node splitting operations occurred when an entry is inserted into a Btree. Then how many nodes are written?
If s splits occur in a Btree, 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 Btree of order 4 and of height 3 will have a maximum of _______ keys.
A Btree of order m of height h will have the maximum number of keys when all nodes are completely filled. So, the Btree will have n = (m^{h+1} – 1) keys in this situation. So, required number of maximum keys = 4^{3+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 Btree can hold both the data values and pointers. So Btree is used as an external memory data structure.
Btree of order n is a ordern multiway tree in which each nonroot node contains __________
A nonroot node in a Btree of order n contains at least (n – 1)/2 keys. And contains a maximum of (n – 1) keys and n sons.
A BTree 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.
CONCEPT:
Btree is a selfbalancing search tree that allows all operations i.e. searching, insertion, deletion in logarithmic(log) time.
Key Points
A Btree of order m must satisfy the following properties:
Hence, if a node has K children in B tree, then the node contains exactly k1 keys.
A BTree 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
Concept:
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 worstcase root node will also be broken into two parts. Since we have 4 levels, then 5 new nodes will be created
Additional Information:
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.
Key Points
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
1 videos51 docs31 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
1 videos51 docs31 tests









