a dynamic lookup scheme for bursty access patterns_infocom2001.ps

本函数的作用就是把读取内存的物理地址,之后找到物理页面的首地址返回过来...它专门找物理地址的 具体东西很多都用汇编编写.好像C很难完成吧 毕竟要用一些调用的 ...哈哈 后面的程序会调用啦 因为每一

Fj(n)p Fo(\))12 b Fp(time)g(where)0 65 y Fj(n)j Fp(is)f(the)h(number)g
(of)f(items.)27 b(\(It)14 b(is)h(suggested)f(that)g(one)h(can)0
115 y(wait)d(for)g(a)h(number)g(of)f(such)h(changes)g(to)f(accumulate)i
(before)0 164 y(reconstructing)7 b(the)h(tree.\))k(Similar)c(search)h
(times)f(are)h(achie)o(v)o(ed)0 213 y(by)h([10])f(at)i(the)f(cost)g(of)
g(e)o(v)o(en)h(higher)f(reconstruction)e(time.)42 271
y Fl(Contrib)o(utio)o(ns.)51 b Fp(In)15 b(this)f(paper)h(we)g(present)g
(a)h(ne)o(w)f(data)0 320 y(structure)c(which)h(we)h(call)f(a)h
Fl(Biased)f(Skip)g(List)p Fp(,)g(or)g(BSL.)h(BSL)0 370
y(e)o(xploits)k(the)i(access)h(probabilities)c(and)j(achie)o(v)o(es)h
(a)f(search)0 419 y(time)10 b(similar)f(to)h(the)f(abo)o(v)o(e)i
(scheme.)k(In)10 b(addition,)e(it)h(adapts)h(to)0 468
y(changes)i(in)e(the)g(access)j(pattern)d(and)h(therefore)g(is)f
(suitable)g(for)0 518 y(highly)j(dynamic)h(en)n(vironments)g(where)h
(the)g(access)h(patterns)0 567 y(are)f(b)o(ursty)m(.)23
b(It)14 b(has)g(been)g(observ)o(ed)h(in)e(man)o(y)i(circumstances)0
617 y(that)c(access)j(patterns)d(do)h(sho)o(w)f(a)h(highly)e(dynamic)i
(character)n(,)0 666 y(i.e.)j(the)c(\252working)e(set\272)i(is)g(quite)
e(small,)j(is)e(subject)h(to)f(change,)0 715 y(and)i(the)g(access)j
(probabiliti)o(es)10 b(are)j(not)f(static)g(o)o(v)o(er)g(long)f(peri-)0
765 y(ods)h(of)g(time)g([2].)19 b(In)12 b(such)g(circumstances,)j(BSL)d
Fl(self)g(adjusts)0 814 y Fp(to)j(access)i(probabilities)c(dynamically)
i(without)e(resorting)h(to)0 864 y(complete)d(reconstruction.)42
921 y(BSL)f(is)g(based)h(on)f(the)h(Skip)e(List)h(data)h(structure)f
([11].)j(Skip)0 970 y(Lists)c(are)h(simple,)g(randomized)f(data)h
(structures)f(which)g(do)g(not)0 1020 y(require)15 b(comple)o(x)h
(balancing)f(operations.)27 b(Their)16 b(simplicity)0
1069 y(often)g(allo)o(ws)h(them)g(to)f(outperform)g(alternati)o(v)o(e)g
(data)h(struc-)0 1119 y(tures)e(in)f(practice.)28 b(Skip)14
b(Lists)h(support)e Fj(O)q Fo(\(log)7 b Fj(n)p Fo(\))15
b Fp(e)o(xpected)0 1168 y(time)e(search,)i(insert)d(and)g(delete)h
(operations)f(for)g(uniform)g(ac-)0 1217 y(cess)i(patterns.)19
b(Ho)o(we)o(v)o(er)n(,)14 b(the)o(y)f(do)f(not)g(distinguish)d(between)
0 1267 y(ke)o(ys)15 b(based)g(on)g(the)f(access)j(frequenc)o(y)m(.)27
b(BSL)15 b(impro)o(v)o(es)g(the)0 1316 y(Skip)8 b(List)h(by)g(e)o
(xploiting)e(the)h(bias)h(in)g(the)g(access)i(pattern.)h(This)0
1366 y(is)c(done)g(by)f(ranking)g(the)h(ke)o(ys)g(according)g(to)g(the)
f(number)h(of)g(ac-)0 1415 y(cesses)15 b(and)e(partitioning)d(them)k
(into)d(dynamic)j(classes)g(based)0 1464 y(on)c(their)f(current)h
(rank.)42 1522 y(W)m(e)j(consider)g(two)g(fundamentally)f(important)g
(access)j(pat-)0 1571 y(terns,)10 b(and)h(adapt)f(BSL)h(to)e(each)j(to)
d(obtain)g(ef)o(\256cient)i(solutions.)0 1637 y(1.)21
b Fl(Independently)13 b(ske)o(wed)h(access)h(patterns.)23
b Fp(Certain)13 b(items)0 1686 y(are)g(accessed)h(more)e(than)g(others)
f(b)o(ut)h(the)f(access)j(frequencies)0 1736 y(remain)9
b(relati)o(v)o(ely)f(stable)g(o)o(v)o(er)h(time.)k(This)8
b(is)g(the)h(type)f(consid-)0 1785 y(ered)h(in)f([1],)h(where)h(an)f
(ele)o(gant)f(solution)f(is)h(gi)o(v)o(en.)13 b(W)m(e)c(present)0
1834 y(a)g(v)o(ariant)g(of)f(BSL)h(that)g(pro)o(vides)f(a)h(solution)e
(for)h(this)g(case;)j(this)0 1884 y(gi)o(v)o(es)f(insight)e(into)h(our)
g(approach)h(for)g(b)o(ursty)f(access)j(patterns,)0 1933
y(which)e(is)g(our)g(main)g(focus.)0 1983 y(2.)21 b Fl(Bursty)9
b(access)h(patterns.)i Fp(A)c(fe)o(w)h(items)g(get)g(\252hot\272)g(for)
f(short)0 2032 y(periods)14 b(of)g(time)h(and)g(are)g(accessed)i(v)o
(ery)e(frequently)m(.)26 b(Such)0 2081 y(patterns)13
b(ha)o(v)o(e)i(been)f(observ)o(ed)g(in)f(v)o(arious)g(applications)f
(in)h(a)0 2131 y(number)j(of)g(studies,)i(such)e(as)h([2],)h([3].)31
b(There)17 b(are)g(a)g(num-)0 2180 y(ber)11 b(of)g(data)g(structures)g
(\([12],)f([13]\))g(that)h(are)g(designed)g(to)f(e)o(x-)0
2230 y(ploit)g(such)j(biases,)g(and)f(pro)o(vide)f(similar)h
(\(amortized\))g(search)0 2279 y(times.)20 b(These)14
b(data)f(structures)f(perform)g(comple)o(x)h(balancing)0
2328 y(schemes)18 b(which)d(hinder)g(their)g(practical)h(performance.)
30 b(W)m(e)0 2378 y(present)10 b(a)h(v)o(ariant)f(of)g(BSL)h(that)e(a)o
(v)o(oids)i(such)f(balancing)g(oper)o(-)0 2427 y(ations,)i(and)g
(employs)f(a)h(no)o(v)o(el)g(lazy)g(maintenance)h(scheme)g(to)0
2477 y(pro)o(vide)f(fast)h(insertion)f(and)h(deletion)f(of)h(ke)o(ys.)
22 b(Our)13 b(mainte-)0 2526 y(nance)g(scheme)h(should)d(not)h(be)g
(confused)g(with)g(those)g(that)f(do)0 2575 y(not)g(re\257ect)j
(changes)f(in)e(the)h(access)j(probabilities)10 b(to)i(the)g(data)0
2625 y(structure)i(immediately)m(,)j(which)d(for)g(highly)f(b)o(ursty)h
(accesses)0 2674 y(can)d(be)g(unacceptable.)p 1229 -24
493 2 v 1228 25 2 50 v 1320 10 a(Range)p 1517 25 V 117
w(Ne)o(xt)g(hop)p 1720 25 V 1229 27 493 2 v 1228 76 2
50 v 1253 62 a Fo([0000)d Fn(\000)i Fo(0001])p 1517 76
V 114 w Fp(b)p 1720 76 V 1228 126 V 1253 111 a Fo([0010)e
Fn(\000)i Fo(0011])p 1517 126 V 115 w Fp(c)p 1720 126
V 1228 175 V 1253 160 a Fo([0100)e Fn(\000)i Fo(0111])p
1517 175 V 114 w Fp(b)p 1720 175 V 1228 225 V 1253 210
a Fo([1000)e Fn(\000)i Fo(1001])p 1517 225 V 114 w Fp(d)p
1720 225 V 1228 274 V 1253 259 a Fo([1010)e Fn(\000)i
Fo(1111])p 1517 274 V 115 w Fp(a)p 1720 274 V 1229 276
493 2 v 1271 348 a Fq(Fig.)f(2.)18 b(Sample)8 b(table)g(of)g(ranges)
1041 486 y Fp(Both)k(v)o(ariants)g(of)h(BSL)h(require)f
Fj(O)q Fo(\()p Fj(n)p Fo(\))g Fp(space,)j(and)d(can)h(be)999
536 y(constructed)8 b(in)g Fj(O)q Fo(\()p Fj(n)p Fo(\))h
Fp(e)o(xpected)g(time)g(when)f(ke)o(ys)h(are)g(gi)o(v)o(en)g(in)999
585 y(sorted)j(order)n(.)17 b(The)12 b(ke)o(ys)g(are)g(ranked)g(1)g
(through)e Fj(n)h Fp(according)999 635 y(to)k(ho)o(w)h(frequently)e(or)
i(recently)f(the)o(y)h(ha)o(v)o(e)h(been)f(accessed.)999
684 y(Searching)f(for)f(a)i(ke)o(y)f Fj(k)h Fp(takes)e
Fj(O)q Fo(\(log)7 b Fj(r)q Fo(\()p Fj(k)q Fo(\)\))15
b Fp(e)o(xpected)h(time,)999 733 y(where)10 b Fj(r)q
Fo(\()p Fj(k)q Fo(\))f Fp(denotes)h(the)f(rank)g(of)g(the)g(ke)o(y)m(.)
k(Because)e(the)e(max-)999 783 y(imum)h(rank)f(is)h Fj(n)p
Fp(,)g(all)f(operations)g(ha)o(v)o(e)h(a)g(worst)f(case)i(e)o(xpected)
999 832 y(bound)h(of)g Fj(O)q Fo(\(log)7 b Fj(n)p Fo(\))13
b Fp(as)g(with)f(Skip)g(Lists)h(and)g(other)f(ef)o(\256cient)999
882 y(data)f(structures)f(\261)g(which)f(is)i(optimal.)999
934 y Fi(Organization)j(of)g(the)h(Paper)l(.)53 b Fp(In)14
b(the)h(follo)o(wing)d(section,)999 984 y(we)g(describe)f(our)g
(problem)g(more)g(formally)f(and)i(e)o(xplain)f(ho)o(w)999
1033 y(BSL)k(works.)23 b(In)14 b(Section)g(III)g(we)g(describe)h(and)f
(analyze)h(the)999 1082 y(cost)10 b(of)g(construction)e(and)j(search.)j
(In)9 b(Section)h(IV)g(we)h(in)n(v)o(esti-)999 1132 y(gate)d(dynamic)h
(BSL.)g(Section)e(V)i(presents)f(some)h(e)o(xperimental)999
1181 y(results.)1302 1279 y(I)r(I)r(.)23 b(P)r Fq(R)r(E)r(L)r(I)r(M)r
(I)r(N)q(A)r(R)r(I)r(E)r(S)999 1353 y Fi(The)11 b(Setup.)k
Fp(W)m(e)c(consider)f(two)g(types)g(of)h(searches;)h(those)e(us-)999
1402 y(ing)i(e)o(xact)h(ke)o(y)f(matching)g(and)g(those)g(using)f
(pre\256x)h(matching.)999 1452 y(W)m(e)d(assume)h(we)g(are)f(gi)o(v)o
(en)g(a)g(set)g(of)f Fl(rules)h Fj(R)i Fo(=)h Fn(f)p
Fj(R)1767 1458 y Fk(1)1785 1452 y Fj(;)7 b(:)g(:)g(:)e(;)i(R)1910
1458 y Fh(k)1929 1452 y Fn(g)999 1501 y Fp(and)12 b(we)h(are)g(looking)
d(for)h(a)i(rule)e(that)h(\252matches\272)i(a)e(tar)o(get)g(ad-)999
1551 y(dress)17 b Fj(A)p Fp(.)1142 1535 y Fx(1)1189 1551
y Fp(In)f(the)g(case)i(of)e(e)o(xact)h(matching,)h(each)f(rule)f
Fj(R)1937 1557 y Fh(i)999 1600 y Fp(consists)c(of)g(a)g(\256x)o(ed)h
(length)e(bit)f(string)h(and)h(an)h(associated)f(ac-)999
1649 y(tion.)19 b(Address)13 b Fj(A)g Fp(matches)h(a)f(rule)f(if)g(it)g
(bitwise)g(matches)h(the)999 1699 y(bit)g(string)g(of)g(the)h(rule)g
(\261)f(this)g(is)h(ob)o(viously)e(re)o(gular)i(equality)999
1748 y(matching)f(with)g(numeric)h(ke)o(ys.)23 b(F)o(or)14
b(pre\256x)f(matching,)i(each)999 1797 y(rule)c Fj(R)1107
1803 y Fh(i)1131 1797 y Fp(consists)f(of)h(a)g(v)o(ariable)g(length)f
(bit)f(string)h(with)f(an)j(as-)999 1847 y(sociated)g(action,)f(where)h
(the)f(bit)g(string)f(corresponds)h(to)f(an)i(IP)999
1896 y(address)g(pre\256x.)17 b(Address)12 b Fj(A)f Fp(matches)i(a)f
(rule)f(if)g(the)g(rule')n(s)g(bit)999 1946 y(string)f(is)h(a)g
(pre\256x)g(of)g Fj(A)p Fp(.)k(When)c(multiple)f(rules)g(match)i(an)f
(ad-)999 1995 y(dress,)g(the)f(rule)f(with)g(the)h(longest)f(matching)h
(pre\256x)g(is)f(chosen.)1041 2048 y(T)m(o)g(facilitate)g(pre\256x)g
(matching)h(with)e(BSL,)i(the)g(pre\256x)o(es)g(are)999
2097 y(represented)18 b(as)f(non-o)o(v)o(erlapping)e(interv)o(als)h(in)
h(the)g(address)999 2147 y(space,)c(as)e(in)f([6])h(and)f([1].)k(W)m(e)
e(borro)o(w)d(the)i(process)g(for)f(trans-)999 2196 y(lating)j(the)g
(pre\256x)o(es)i(to)e(interv)o(als)g(from)g(these)h(papers)h(and)e(do)
999 2245 y(not)c(go)g(into)g(the)g(details)g(of)h(this)e(translation;)g
(we)i(on)o(y)g(note)f(that)999 2295 y(addition)e(and)h(remo)o(v)o(al)h
(of)f(pre\256x)o(es)h(requires)f(us)h(to)f(reconstruct)999
2344 y(these)j(interv)o(als.)1041 2397 y(The)20 b(number)g(of)g(interv)
o(als)f(resulting)f(from)i(the)g(transla-)999 2446 y(tion)12
b(of)h(pre\256x)o(es)h(can)f(be)h(at)f(most)g(twice)g(the)g(number)f
(of)h(pre-)999 2496 y(\256x)o(es,)j(since)f(each)g(pre\256x)f(can)h
(contrib)o(ute)e(at)h(most)g(two)f(right)999 2545 y(end)h(points)f(to)h
(the)g(set)g(of)g(interv)o(als.)24 b(In)14 b(Figure)g(II)g(we)g(sho)o
(w)1026 2626 y Fg(1)1043 2638 y Fq(W)m(e)8 b(assume)e
Ff(A)i Fq(is)g(an)f(IP)h(address,)e(b)o(ut)h(generally)g(it)g(may)g(be)
g(any)f(item)h(from)999 2674 y(a)h(totally)g(ordered)f(uni)o(verse.)p
eop
%%Page: 3 3
3 2 bop 1935 -100 a Fx(3)0 16 y Fp(the)18 b(translation)f(of)h(the)g
(pre\256x)o(es)h(from)f(Figure)g(I)g(into)f(non-)0 65
y(o)o(v)o(erlapping)10 b(interv)o(als.)15 b(Each)d(of)f(the)f(non-o)o
(v)o(erlapping)g(inter)o(-)0 115 y(v)o(als)g(is)g(stored)f(as)i(a)f(ke)
o(y)g(in)g(BSL,)g(thus)f(each)j(ke)o(y)e(contains)f(two)0
164 y(end)15 b(points)f(to)g(represent)h(the)g(interv)o(al.)27
b(Since)15 b(the)g(interv)o(als)0 213 y(are)c(non-o)o(v)o(erlapping,)e
(we)i(de\256ne)g(an)g(ordering)e(between)i(ke)o(ys)0
263 y(as)i(follo)o(ws.)20 b(F)o(or)13 b(ke)o(ys)g Fj(i;)7
b(j)r Fp(,)14 b(we)f(say)g Fj(i)k(<)g(j)e Fp(if)d(the)h(right)e(\(sec-)
0 312 y(ond\))h(endpoint)f(of)h Fj(i)i Fp(is)e(less)h(than)f(the)h
(left)f(\(\256rst\))g(endpoint)f(of)0 362 y Fj(j)r Fp(,)h(implying)c
(that)i(all)g(IP)h(addresses)g(within)e Fj(i)i Fp(are)g(smaller)g(than)
0 411 y(those)j(within)e Fj(j)r Fp(.)24 b(An)14 b(address)g(can)h(be)f
(compared)h(to)e(a)h(a)h(ke)o(y)0 460 y(in)c(a)g(similar)g(way)g(as)g
(well;)g(the)g(address)h(is)f(said)g(to)f(be)i(smaller)0
510 y(than)j(a)g(ke)o(y)g(if)g(it)f(is)h(less)h(than)e(the)h(ke)o(y')n
(s)g(left)g(endpoint,)g(and)0 559 y(greater)f(if)f(greater)h(than)f
(its)g(right)g(endpoint.)21 b(The)15 b(address)f(is)0
609 y(said)9 b(to)g Fl(matc)o(h)g Fp(\(be)g(equal)h(to\))e(a)i(ke)o(y)f
(if)g(it)f(falls)h(within)e(the)i(ke)o(y')n(s)0 658 y(interv)o(al.)j(W)
m(e)f(then)f(make)g(the)h(follo)o(wing)c(observ)o(ation.)83
717 y Fl(Observation)j(1:)20 b Fp(Gi)o(v)o(en)d(the)g(abo)o(v)o(e)h
(ordering)e(between)0 767 y(ke)o(ys)g(and)f(between)h(ke)o(ys)g(and)f
(addresses,)k(we)d(can)g(consider)0 816 y(the)10 b(ke)o(ys)h(in)f(a)h
(BSL)g(as)g(inte)o(gers)g(and)g(perform)f(a)h(pre\256x)g(search)0
866 y(in)j(the)h(same)h(way)f(we)g(perform)g(an)g(e)o(xact)h(matching)e
(search.)0 915 y(F)o(or)g(e)o(xact)h(matches,)h(ke)o(ys)e(stored)g(in)f
(the)h(data)g(structure)f(and)0 964 y(the)f(tar)o(get)h(address)g
Fj(A)f Fp(are)i(both)d(\256x)o(ed)i(length)e(bit)h(strings)f(and)0
1014 y(often)f(we)i(refer)g(to)e Fj(A)h Fp(as)h(a)g(ke)o(y)m(,)g(pro)o
(viding)d(there)i(is)g(no)f(confu-)0 1063 y(sion.)0 1123
y Fi(Ef\256ciency)m(.)37 b Fp(Our)18 b(main)g(concern)h(is)f
(throughput;)h(i.e.)37 b(we)0 1172 y(would)8 b(like)h(to)h(minimize)g
(total)e(lookup)h(time)h(o)o(v)o(er)g(a)h(sequence)0
1221 y(of)i(lookups.)20 b(In)13 b(most)f(applications)g(certain)h
(pre\256x)o(es)h(are)g(ac-)0 1271 y(cessed)19 b(much)e(more)h
(frequently)e(than)h(others,)i(gi)o(ving)d(a)i(bi-)0
1320 y(ased)c(distrib)o(ution)o(.)k(The)c(distrib)o(ution)9
b(may)14 b(either)e(\(i\))g(change)0 1370 y(rapidly)m(,)17
b(as)f(in)g(the)f(case)j(of)d(end)h(routers)g(to)f(which)g(connec-)0
1419 y(tions)10 b(are)j(short)e(li)o(v)o(ed)g(b)o(ut)g(frequent)g
(\(such)h(as)g(HTTP\),)h(or)n(,)f(\(ii\))0 1468 y(may)j(remain)g
(relati)o(v)o(ely)e(stable)h(as)h(in)f(the)g(case)i(of)e(backbone)0
1518 y(routers.)21 b(Our)13 b(data)g(structure,)g(the)g(Biased)h(Skip)e
(List,)i(adapts)0 1567 y(to)c(maximize)h(throughput)d(once)j(the)g
(type)f(of)g(traf)o(\256c)h(pattern)f(is)0 1617 y(identi\256ed.)0
1676 y Fi(Regular)g(Skip)f(List)g(in)g(a)h(Nutshell.)25
b Fp(A)9 b(Skip)g(List)g(is)h(a)g(search)0 1726 y(data)16
b(structure)f(for)g Fj(n)h Fp(ordered)f(ke)o(ys)h([11].)28
b(It)15 b(allo)o(ws)g(linear)0 1775 y(e)o(xpected)j(time)f
(construction)e(\(if)h(ke)o(ys)h(are)h(gi)o(v)o(en)e(in)g(sorted)0
1824 y(order\))f(and)g(logarithmic)f(e)o(xpected)i(time)f(search,)j
(insert)d(and)0 1874 y(delete)c(operations.)j(T)m(o)c(construct)g(a)i
(Skip)e(List,)h(we)g(\256rst)f(make)0 1923 y(up)k(le)o(v)o(el)g
Fo(log)6 b Fj(n)p Fp(,)16 b(which)d(is)h(a)g(sorted)g(linked)e(list)h
(of)h(all)f(of)h(the)0 1973 y(ke)o(ys)e(\(for)e(simplicity)g(of)h
(notation,)g(throughout)d(the)k(paper)f(we)0 2022 y(write)e
Fo(log)d Fj(n)j Fp(instead)g(of)g Fn(d)p Fo(log)432 2032
y Fk(2)458 2022 y Fj(n)p Fn(e)p Fp(\).)k(Le)o(v)o(els)d
Fo(\(log)d Fj(n)p Fo(\))e Fn(\000)g Fo(1)p Fj(;)i(:)g(:)g(:)f(;)h
Fo(1)0 2071 y Fp(are)14 b(b)o(uilt)f(randomly)f(in)i(a)g(bottom-up)e
(fashion.)22 b(Each)15 b(le)o(v)o(el)e Fj(i)0 2121 y
Fp(is)e(a)g(sorted)f(linked)g(list)f(consisting)h(of)g(a)i(subset)e(of)
h(the)f(ke)o(ys)h(in)0 2170 y(le)o(v)o(el)g Fj(i)f Fo(+)g(1)g
Fp(obtained)g(as)i(follo)o(ws:)g(each)g(ke)o(y)e(in)h(le)o(v)o(el)g
Fj(i)f Fo(+)f(1)i Fp(is)0 2220 y(copied)d(to)f(le)o(v)o(el)h
Fj(i)g Fp(independently)e(with)h(probability)e Fo(1)p
Fj(=)p Fo(2)p Fp(.)12 b(Each)0 2269 y(ke)o(y)d(has)g(v)o(ertical)g
(pointers)f(to)g(and)h(from)f(its)g(copies)h(\(if)g(the)o(y)f(e)o(x-)0
2318 y(ist\))i(on)g(adjacent)h(le)o(v)o(els.)k(Because)d(there)f(are)h
Fo(log)6 b Fj(n)11 b Fp(le)o(v)o(els,)g(we)0 2368 y(e)o(xpect)f(to)f
(ha)o(v)o(e)i(one)f(ke)o(y)f(in)h(le)o(v)o(el)f Fo(1)p
Fp(.)k(Note)d(that)f(since)h(the)f(con-)0 2417 y(struction)g(is)g
(randomized,)i(it)e(only)g(makes)i(sense)h(to)d(talk)h(about)0
2467 y(e)o(xpected)j(v)o(alues)f(rather)f(than)h(absolute)f(numbers)h
(when)g(talk-)0 2516 y(ing)d(about)h(the)g(number)g(of)g(ke)o(ys)h(in)e
(a)i(le)o(v)o(el.)42 2575 y(T)m(o)g(search)i(for)e(a)i(ke)o(y)e
Fj(k)q Fp(,)i(we)f(start)g(from)f(the)h(smallest)g(\(left-)0
2625 y(most\))j(ke)o(y)g(in)f(the)h(top)f(le)o(v)o(el)h(\(le)o(v)o(el)g
(1\).)28 b(On)14 b(each)j(le)o(v)o(el,)f(we)0 2674 y(go)e(right)g
(until)f(we)i(encounter)g(a)g(ke)o(y)g(which)f(is)h(greater)g(than)999
16 y Fj(k)q Fp(.)k(W)m(e)13 b(then)f(take)g(a)h(step)f(to)g(the)g(left)
g(and)g(go)g(do)o(wn)g(one)g(le)o(v)o(el)999 65 y(\(which)h(lea)o(v)o
(es)i(us)f(in)f(a)h(ke)o(y)f(less)h(than)f Fj(k)q Fp(\).)23
b(The)14 b(search)h(ends)999 115 y(as)e(soon)e(as)h Fj(k)h
Fp(is)f(found,)f(or)h(when,)g(at)g(the)g(lo)o(west)f(le)o(v)o(el,)i(a)f
(ke)o(y)999 164 y(greater)h(than)f Fj(k)i Fp(is)e(reached.)21
b(T)m(o)13 b(delete)f(a)h(ke)o(y)m(,)h(we)f(perform)g(a)999
213 y(search)h(to)f(\256nd)g(its)f(highest)g(occurrence)i(in)f(the)g
(structure)f(and)999 263 y(delete)g(it)f(from)h(e)o(v)o(ery)h(le)o(v)o
(el)f(it)f(appears.)19 b(T)m(o)11 b(insert)h(a)g(ne)o(w)g(ke)o(y)999
312 y Fj(k)q Fp(,)h(we)g(\256rst)f(search)h(for)f(it)f(in)g(the)h(data)
h(structure)e(to)h(locate)g(the)999 362 y(correct)e(place)h(to)e
(insert)h(it)f(in)g(the)h(bottom)f(le)o(v)o(el.)k(Once)d(the)g(ke)o(y)
999 411 y(is)k(inserted)g(into)f(the)h(bottom)f(le)o(v)o(el,)j(a)e
(fair)g(coin)g(is)g(tossed)g(to)999 460 y(decide)c(whether)f(to)f(copy)
h(it)f(to)h(the)f(le)o(v)o(el)i(abo)o(v)o(e.)j(If)c Fj(k)h
Fp(is)f(indeed)999 510 y(copied,)14 b(the)g(procedure)f(is)g(repeated)h
(iterati)o(v)o(ely)e(for)h(the)g(ne)o(xt)999 559 y(le)o(v)o(el,)e
(otherwise)f(the)g(insertion)f(is)h(complete.)1210 675