178 views
consider a ABC university and the relation took(StudentID, CourseNo, Quarter, Year, Units, Grade) contains the grades for the courses completed by ABC students during the last 20 years. For simplicity, assume that there are 25,000 students enrolled each quarter, and that each student takes four courses per quarter, and that there are four quarters each year. Then we get a total of 8,000,000 records. If 10,000 new students enter ABC every year, we can assume that in took there are 200,000 different students, each identified by its StudentID. On the average, a student took 40 different courses. The file blocks hold 2048 bytes and each took tuple requires 50 bytes.
The table has a primary index on StudentID. If the StudentID index is a B+ tree with order n = 101, how many levels does the B+ use, in the worst case. (n denotes the maximum number of pointers in a node.)

Ans 3

1 comment

There are 200,000 different student on an average in 20 years .

each student has unique student id .

The table has primary index on student_id which means it has 200000 tuples .

So total number of levels $\left \lceil \log_{101}200000 \right \rceil=3$

alternatively ,

0th  level has $1$ node.(root)

1st level has $101$ node .

2nd level has $101*101$ node

3rd level has $101*101*101$ node.

So, $1+101+101*101+101*101*101$ this will include all the rows which need at least 3 levels considering root at 0th level .

(But I think the key should be combination of student_id + Course_Id as 40 course they can take which increases rows )