DBMS - me

Question

Suppose a phone book contain 500 pages and each page can contain upto 500 records. Suppose we want to search for a particular name in a phone book. Give a worst case bound on number of pages that must be looked to perform a search using an index for the name of the first entry of each page.

Comments

it will be 1+$\log_2 500$ = 10

---

2 is given

Answer 1

here index is on the names so we have to visit only 2 pages 1st for searching the name on index that is fisrt index page and second is the record page containing the name in worst case bound so answer will be 2.

Comments

don't understand ??

---

suppose you want to search for a name let me take ZZZA(random name for considering as worst case in alhabetic order) now its given that the indext page is given by the name of the first entry of each page.

so to find ZZZA suppose index is given 500 numbered page as first entry as ZAAA... so u don't need to go through each pags.. you just need to reffer index page find the relevent 1st entry and then directly go to that page (which is 2nd page to be reffered regardless the page num.) find the name there by linear search of all 500 names of that page.

i hope is clear now. :}