Database Management, fall 04, Exercises 3(18.11.2004)

• Table T is implemented as a pile (unordered sequential). It has a dense ISAM organised secondary index based on its primary key K. Which of the following queries may benefit of the use of the index. How would you use the index in these cases?
  • select * from T where K=123;
  • select * from T where K!=123;
  • select * from T where K>123;
  • select * from T where K<123;
  • select * from T where K in (123,456,789);
  • select * from T where K not in (123,456,789);
  • select max(K) from T;
  • select * from T where K mod 100=23;
• Let's consider ISAM file organisation just after it has been populated. There are n records. A data page may contain k records but only 50% of space is used. An index page may contain h*k index entries. Which value on n causes the structure to become a 3-level one and how long does it remain a 3 level structure (the maximum value on n). Compute the value on n when k=10, and h=30.
• Records with keys 23, 65, 37, 60, 46, 92, 48, 71, 56, 59, 18, 21, 10, 74, 78, 15, 16, 20 ja 24 are inserted into a B+-tree of order 2 (2..4 keys in an index page and 2..4 records in a data page).
  • Draw the tree after inserts. What is the fill factor (= occupied / all places) in leafs and in index pages?
  • Draw the tree when recors with keys 24, 23, 10 ja 20 are deleted? What is the fill factor (= occupied / all places) in leafs and in index pages?
• Let's consider a B+-tree. Leafs may contain k data records and index pages h*k keys.
  • How many data records there are in a B+ -tree of 3 levels at least and at most.
  • How many data records there are in a B+ -tree of 4 levels at least and at most.
  • Compute the limits when k=10, and h=30.
• Table T is stored as a pile. It has n rows which are stored in n/k pages. Secondary index based on column S is to be considered. Column S has b distinct values. Values are evenly distributed. Let's consider the query

  select * from T where S='something'

  The index should be organised as ISAM. Let n be so big that the index would have 3 levels. Which value of b would cause the use of the index to be more efficient than scanning the whole file? The seek time for the disk is 6ms, rotation delay 2.4 ms and block transfer time 0.2 ms.