Exercise 108 assume that you have just built a dense b tree

Question

Exercise 10.8 Assume that you have just built a dense B+ tree index using Alternative (2) on a heap file containing 20,000 records. The key field for this B+ tree index is a 40-byte string, and it is a candidate key. Pointers (Le., record ids and page ids) are (at most) 10

• byte values. The size of one disk page is 1000 bytes. The index built in a bottom-up fashion usingbulk-loading algorithm, and the nodes at each level were filled up much as possible.

1. How many levels does the resulting tree have?

2. For each level of the trec, how many nodes are that level?

How many levels would the resulting tree have if key compression is llsed and it reduces the average size of each key in an entry to 10 bytes?

sid name login age gpa

53831	Maclayall	maclayan@music	11	1.8
53832	Guldu	guldu@music	12	3.8
53666	Jones		18	3.4
53901	Jones		18
53902	Jones	jones@physics	18	3.4
53903	Jones		18	3.4
53904	Jones	jones(ggenetics	18	3.4
53905	Jones	jones@astro	18	3.4
53906	Jones	jones@chem	18	3.4
53902	Jones		18	3.8
53688	Smith	smith@ee	19	3.2
53650	Smith	smith@math	19	3.8
54001	Smith	smith@ee	19	3.5
54005	Smith	smith@cs	19	3.8
54009	Smith		19	2.2

Figure 10.30 An Instance of the Students Relation

4. How many levels would the resulting tree have without key compression but with all pages 70 percent full?