indexing

Question

Comments

whether the first entry of the page is sorted or not???

---

nothing is said about whether its sorted or unsorted. pls explain with a diagram.

Answer 1

is it 2?

Comments

how its 2 ...according me 9 is coming? can u please ur approach

---

it is phone book so it is ordered. there are 500 pages and each page can store 500 records. as key + pointer to block <= record, we can store it like primary indexing. for each page we can store key and pointer so for 500 pages we can stores pointer in 1 page. so 1 page acces to see index and 1 more page access the record.

---

but search is taken place here based on the name of first entry of each page....which is just like sparse indexing ...

each block contain 500 records and here it is 500 pages .

so 1 index is enough to store all pages.

total block=501

avg. no block access=log B +1=9+1=10

in worst case linear search =501/2=251 search....if m wrong plz correct me

---

i dont understand how you take it but i will explain in detail my approach. but first i want to knw what is correct answer. because may be ur approch correct and mine wrong.

some one who knows what is correct answer please post.

---

yaa that may be write....whats the ans...@Arnabi

---

@arch  ans given is 2.

Can you explain this line  "as key + pointer to block <= record, we can store it like primary indexing" more?

from where in the question  are you getting key value and block pointer size?

---

suppose u have table employee(ssn , first name , last name , salary , department , dob , address , phone no)

each row of this table is called record. in block we store full row but in index block we store only primary key(if primary indexing is used) + block pointer so index block contain only (ssn , block pointer ) which will be less in size then particular row .

if 1 page contain 500 records then 1 page contain (page no. of 500 pages + enchor key)which is analogous to block pointer and ssn respectively. so for seeing correct page we first access index page and then one more access to access that particular page in which particular record which we are looking is present so 2 page access required.

---

Isn't is ceil(500) i.e 3 pages to be loked up?

---

@arch thanks :)

 So, index block  contains name of first entry of each page and page no. Thus 1 page access for the index itself + 1 page for the particular entry we wanted to search. Total page to look up =2.

---

no question asked only for no. of page access thats y record access is ignored.