cdb (mjukvara)

För annan användning, se CDB (disambiguation) .

cdb , förkortning för "konstant databas", syftar på både ett bibliotek och ett dataformat skapat av Daniel J. Bernstein . cdb fungerar som en associativ array på disken , mappar nycklar till värden och tillåter att flera värden lagras för en enda nyckel. En konstant databas tillåter bara två operationer: skapande och läsning. Båda operationerna är designade för att vara mycket snabba och mycket tillförlitliga. Eftersom databasen inte ändras medan den används kan flera processer komma åt en enda databas utan låsning. Dessutom, eftersom alla ändringar skapar en ersättningsdatabas, kan den dra fördel av UNIX-filsystemets semantik för att ge en garanti för tillförlitlighet.

Postpositioner, nyckel- och värdelängder och hashvärden är 32-bitars kvantiteter och måste därför passa in i 4 gigabyte. cdb används av djbdns , fastforward, mess822, qmail och ucspi-tcp för att ge mycket effektiv, pålitlig och enkel dataåtkomst.

Strukturera

En databas innehåller en hel datamängd (t.ex. en enda associativ array) i en enda datorfil . Den består av tre delar: en rubrik med fast storlek, data och en uppsättning hashtabeller . Uppslagningar är endast utformade för exakta nycklar, även om andra typer av sökningar kan utföras genom att skanna hela databasen. Uppslagningar utförs med hjälp av följande algoritm :

• Hasha nyckeln.
• Bestäm vid vilken hash-tabell och plats denna post ska placeras.
• Testa den angivna luckan i hashtabellen.
  • Om platsen är tom finns posten inte. Avbryt sökningen.
  • Om slotens hash matchar nyckelns hash, sök till posten. Läs och jämför nyckeln. Om det stämmer överens har data hittats, så avsluta sökningen.
  • Rekordet finns inte i den här luckan. Fortsätt till nästa lucka, linda runt till början av hashtabellen om det behövs.

För uppslagningar av nycklar med flera värden kan ytterligare värden hittas genom att helt enkelt återuppta sökningen vid nästa lucka.

Formatera

Alla tal – förskjutningar, längder och hashvärden – är 32- bitars heltal utan tecken , lagrade i little endian- format. Nycklar och data anses vara ogenomskinliga bytesträngar och har ingen speciell behandling.

Rubriken med fast storlek i början av databasen beskriver 256 hashtabeller genom att lista deras position i filen och deras längd i luckor. Data lagras som en serie poster, var och en lagrar nyckellängd, datalängd, nyckel och data. Det finns inga regler för justering eller sortering. Posterna följs av en uppsättning av 256 hashtabeller av varierande längd. Eftersom noll är en giltig längd kan det finnas färre än 256 hashtabeller fysiskt lagrade i databasen, men det anses ändå vara 256 tabeller. Hash-tabeller innehåller en serie slots, som var och en innehåller ett hashvärde och en postoffset. "Empty slots" har en offset på noll.

Hashes är osignerade 32-bitars heltal och börjar med värdet 5381. För varje byte av nyckeln multipliceras den aktuella hashen med 33, sedan XOR 'ed med nyckelns aktuella byte. Överflödesbitar kasseras. Slots och bord är trivialt beräknade från hash. Måltabellen är helt enkelt de lägsta åtta bitarna av hashen (dvs. hash modulo 256), och luckan i tabellen är de återstående bitarna av hash modulo tabelllängden (dvs. hash dividerat med 256 modulo table length).

Bibliotek

Den officiella cdb-bibliotekskoden är public domain : de individuella källfilerna är markerade som sådana och är också tillgängliga i public domain djbdns -paketet. Men resten av cdb-paketet brukade vara licensfri programvara , vilket betyder att det måste distribueras ordagrant. Den ovanliga licensieringen och enkelheten i formatet har fått andra att implementera biblioteket på nytt och släppa det under vanligare villkor, som Michael Tokarevs TinyCDB-bibliotek, tillgängligt under den offentliga egendomen.

2009 lades all cdb till allmän egendom.

Noterbart är att skaparen av cdb inte har för avsikt att cdb ska användas som ett delat bibliotek . Detta skiljer sig från praktiskt taget alla liknande dbm- liknande databaser, såsom Berkeley DB .

externa länkar

• cdb officiella cdb-webbplats
• Konstant databas (cdb) Intern detaljerad formatbeskrivning
• QDBM benchmark som jämför cdb med liknande paket