Klausimas, į kurį indeksas neatsako

Turi indeksą, kuris atsako per 1.3 palyginimo. Paklausk jo paprasčiausio dalyko, kokio tik gali paprašyti bibliotekos: išvardyk knygas abėcėlės tvarka.

$ algo gen -n 1000 -seed 3
$ algo ordered -n 6
the first 6 titles, as the index stores them:
  Lažižo
  Rūdovi
  Bąkėbėra Mąbą
  Lėpubė
  Žąčąva Šomū
  Medošibe

the first 6 in alphabetical order:
  Bagogū Guže
  Bamežanė Pako
  Bamila
  Basėrūno
  Batalu
  Batėvovu Sūvi

getting the second list from the index cost a full sort of all 1000 keys.
the index itself could not answer the question at all.

Pirmasis sąrašas nėra netvarkingas dėl klaidos. Jis yra kibirų tvarka — tai yra hashKey(pavadinimas) % kibirų skaičius tvarka, o maišos funkcijos paskirtis yra sunaikinti bet kokį ryšį tarp rakto ir jo skaičiaus. Būtent todėl grandinėlės lieka trumpos. Tvarka nebuvo pamesta — ji buvo sunaikinta tyčia, ir tai ir yra tai, už ką sumokėta.

Antrasis sąrašas gautas surikiavus visus 1 000 raktų. Tai O(n log n) kiekvienam tokiam klausimui — brangiau nei viskas, ką indeksas kada nors sutaupė.

Ko maišos lentelė negali

Ne „daro lėtai". Negali.

klausimas	maišos lentelė
ar yra „Bamila"?	1.3 palyginimo
kokia pirma abėcėlėje?	tik surikiavus viską
kurios prasideda „Ba"?	tik peržiūrėjus viską
kokios 20 eina po „Bamila"?	nėra tokios sąvokos
kokia knyga prieš šitą?	nėra tokios sąvokos
aukščiausias įvertinimas?	tik peržiūrėjus viską

Kiekvienam iš šių klausimų atsakymas yra tas pats: grįžk prie visos aibės. Indeksas nepadeda, nes jis nieko nežino apie tai, kas eina po ko.

Tai nėra trūkumas

Pirmame žingsnyje buvo parašyta: struktūra nusiperka viena, sumoka kita. Čia sandoris matomas iš abiejų pusių:

Maišos lentelė yra geriausia, ką turi vienam klausimui — „ar šis tikslus raktas yra" — ir ji neatsako į jokį kitą.

Nesirinktum jos bibliotekos katalogui, kurį reikia rodyti puslapiais. Rinktumeisi sesijų saugyklai, žodžių dažnių skaičiuoklei, „ar šis vartotojo vardas užimtas".

Klausimas, kuriuo prasideda vienuolikta pamoka

Vienuolikta pamoka pradedama nuo antrojo šio žingsnio sąrašo — bet gauna jį nerikiuodama nieko.

Dvejetainės paieškos medis atsisako O(1): jo paieška kainuoja O(log n), taigi lėčiau nei tavo indeksas. Mainais jis išlaiko tvarką savo struktūroje, o perėjimas nuo mažiausio iki didžiausio yra tiesiog vienas medžio apėjimas.

Tas pats klausimas, į kurį šis indeksas negali atsakyti nė už kokią kainą, vienuoliktoje pamokoje kainuos O(n) ir nė vieno palyginimo daugiau nei reikia kiekvienam elementui aplankyti.

Tai ne „geriau". Tai kita sandorio pusė.