expalin

Question

if we use 3 key ,4 pointer nodes. how many different B tree are there when the data file has 6 records.

Answer 1

First, the six data records can be divided among the B-tree leaves in the following ways: 2-2-2 or 3-3. There are no other ways to divide size records, with 2 or 3 for each leaf.  bcoz of it should be half full  , so we cant divide like 1-5 or 1-1-2-2 , there are only 2 possible way . 

In each of these two cases, there can be only one other node, the root, and it must point to each of the two or three leaves. Again, there are no other ways to structure 2 or 3 leaves, with each interior node having 2 or 3 children. Our conclusion is that there are only two different B-trees for 6 data records.

http://infolab.stanford.edu/~ullman/dbsisols/sol4.html#sol43

Comments

6 records

4 pointer node means 4 leaves or 4 non root node

3 keys i.e. max 3 keys in each node, rt?

Is such tree possible?

Can u draw such a tree?

---

@srestha :

4 pointer node will be pointer to non leaf .

Leaf node doest have node pointer . they have record pointers

and yes 3you are right about 3 keys

---

can you pls explain what is meant by 4 pointer node and what is its significance here??