Lookup Algorithm

2 5 7 8

13 14 15 18

22 24

26 27 28

32 35 38

40 42 45 46

13 22

32 40

26

Find 24

lookup(page p, item x)

if p is a leaf page

if x==p.item[k] return p.pointer[k]

else return NULL

else if x<p.item[1]

return lookup(p.pointer[1], x)

else if for some j p.item[j] <= x < p.tem[j+1]

return lookup(p.pointer[j+1], x)

else return lookup(p.pointer[n+1], x)

/*p.pointer[n+1] is the last pointer in the page*/

Previous slide

Next slide

Back to first slide

View graphic version