Om een sequentieel bestand toegankelijk te maken werkt men met indexen. De 
indexen die ontstaan uit de sleutels kunnen in directe relatie staan tot 
het adres van het betreffende record (zg. directe adressering). Omdat het 
aantal mogelijke sleutelwaarden vaak veel groter is dan het aantal 
voorkomende, betekent dit dat er bij directe adressering vaak grote gaten 
ontstaan, wat inefficient geheugengebruik tot gevolg heeft.

Een oplossing hiervoor biedt het zg. indirect adresseren. Via een sleutel-
transformatie wordt in dit geval het werkelijk optredend aantal sleutel-
waarden afgebeeld op een beperkt adresgebied (hierdoor is er geen directe 
relatie meer tussen sleutel en adres).
De sleuteltransformatie heeft tot doel de omrekening van sleutelwaarden 
naar adressen zodanig uit te voeren dat de verdeling van alle records over 
(beperkt!) beschikbare ruimte statistisch gezien zo gelijkmatig mogelijk 
wordt. Daarnaast dient het aantal synoniemen, dat zijn de sleutels die na 
transformatie hetzelfde adres op leveren, zo beperkt mogelijk te zijn.

Deze synoniemen geven aanleiding tot een nieuw probleem, nl. nu de 
sleutelwaarde bij de indirecte adressering i.t.t. bij de directe adres-
sering NIET meer uniek is, kan het dus voorkomen dat neerdere 
(verschillende) sleutels op hetzelfde adres komen (overflow).
Door de synoniemen middels verwijzingen aan elkaar te koppelen (chained 
overflow) kan men vervolgens alle synoniemen sequentieel doorlopen op zoek 
naar de juiste.
De binning-techniek is een manier om overflow uit te stellen. Een bin of 
bucket is een adreslocatie voor meerdere reords. De randomizer rekent 
a.d.h.v. de sleutelwaarde het bin-adres uit (op de randomizing-techniek 
c.q. hashing-algorithme wordt hier niet ingegaan) en de synoniemen kunnen 
onder hetzelfde adres in de bucket worden gezet. Pas wanneer het bucket 
uitgevuld is met synoniemen wordt een zogeheten overflowbucket in gebruik 
genomen.

Om nu een record met een bepaalde sleutelwaarde te vinden wordt dus eerst 
de bucket berekend a.d.h.v. de sleutel middels het hashing-algorithme en 
daarna wordt de bucket met synoniemen doorzocht tot de juiste sleutel 
wordt gevonden.
Ruwweg wordt het aantal buckets gelijk genomen aan het quotient van de 
bestandsgrootte (aantal records, vaak neemt men dan nog een overhead van 
ca. 30%) en het aantal indexen dat in een bucket kan.
Van dit quotient zoekt men dan nog het naast-grotere priemgetal om 
periodiciteit van de synoniempieken tegen te gaan.
Niettemin heeft men ook bij een gemiddelde bucketbezetting lager dan 100%, 
ook bij een statistisch zuivere randomverdeling van sleutelwaarden over 
het te mappen sleutelwaardengebied al gauw te kampen met overflowbuckets.

Het in formules uitdrukken hoe veel overflowbuckets in gebruik zullen zijn 
bij een bestand ven een bepaalde grootte met gegeven bucketgrootte (of 
eigenlijk bij gegeven indexlengte) is geen sinecure en vanwege de 
gecompliceerdheid van de materie is zal men hierover weinig vinden in de 
vakliteratuur.

Om toch een idee te krijgen hoeveel overflowbuckets in bepaalde omstandig-
heden bij een zuivere verdeling in gebruik zullen zijn, is het programma 
BUCKETS.PRG ontwikkeld. Voor verdere uitleg wordt verwezen naar de uitleg 
die het programma zelf geeft.



F. de Rooij        2 april 1990
Noordzijde 76
2411 RC  BODEGRAVEN