Cdb (software) - cdb (software) - Wikipedia

Pro další použití viz CDB (disambiguation).

cdb, zkratka pro „konstantní databázi“, odkazuje na a knihovna a datový formát vytvořený Daniel J. Bernstein. cdb funguje jako disk asociativní pole, mapování klíčů na hodnoty a umožňuje uložení více hodnot pro jeden klíč. Konstantní databáze umožňuje pouze dvě operace: vytvoření a čtení. Obě operace jsou navrženy tak, aby byly velmi rychlé a vysoce spolehlivé. Protože databáze když se používá, nemění se, více procesů může přistupovat k jedné databázi bez uzamčení. Navíc, protože všechny úpravy vytvářejí náhradní databázi, může využít sémantiku souborového systému UNIX a zajistit tak spolehlivost.

Pozice záznamu, délky klíče a hodnoty a hodnoty hash jsou 32bitové veličiny, a proto se musí vejít do 4 gigabajtů.[1] cdb je používán djbdns, rychle vpřed, nepořádek822, qmail a ucspi-tcp poskytovat vysoce efektivní, spolehlivý a jednoduchý přístup k datům.

Struktura

Databáze obsahuje celou sadu dat (např. Jedno asociativní pole) v jednom počítačový soubor. Skládá se ze tří částí: záhlaví pevné velikosti, data a sada hash tabulky. Vyhledávání je určeno pouze pro přesné klíče, ačkoli jiné typy vyhledávání lze provést skenováním celé databáze. Vyhledávání se provádí pomocí následujícího algoritmus:

  • Zaškrtněte klíč.
  • Určete, u kterého hash stolu a slotu záznam by měl být umístěn.
  • Vyzkoušejte uvedený slot v tabulce hash.
    • Pokud je slot prázdný, záznam neexistuje. Přerušit hledání.
    • Pokud se hash slotu shoduje s hash klíče, vyhledejte záznam. Přečtěte si a porovnejte klíč. Pokud se shodují, data byla nalezena, takže hledání ukončete.
    • Záznam není v tomto slotu. Pokračujte do dalšího slotu a v případě potřeby jej zalomte na začátek tabulky hash.

U vyhledávání klíčů s více hodnotami lze další hodnoty najít jednoduchým obnovením vyhledávání na dalším slotu.

Formát

Všechna čísla - posuny, délky a hodnoty hash - jsou nepodepsaná 32-bit celá čísla, uloženo v malý Endian formát. Klíče a data se považují za neprůhledný bajt struny a nemají žádné zvláštní zacházení.

Záhlaví pevné velikosti na začátku databáze popisuje 256 hashovacích tabulek uvedením jejich polohy v souboru a jejich délky ve slotech. Data se ukládají jako série záznamů, přičemž každá ukládá délku klíče, délku dat, klíč a data. Neexistují žádná pravidla pro zarovnání nebo řazení. Za záznamy následuje sada 256 hashovacích tabulek různé délky. Vzhledem k tomu, že nula je platná délka, může být v databázi fyzicky uloženo méně než 256 hash tabulek, ale přesto se považuje za 256 tabulek. Tabulky hash obsahují řadu slotů, z nichž každý obsahuje hodnotu hash a posun záznamu. „Prázdné bloky“ mají offset nula.

Hash jsou 32bitová celá čísla bez znaménka a začínají hodnotou 5381. Pro každý bajt klíče se aktuální hash vynásobí 33, pak XOR 's aktuálním bajtem klíče. Přepadové bity jsou zahozeny. Automaty a tabulky jsou triviálně počítány z hashů. Cílová tabulka je jednoduše nejnižších osm bitů hash (tj. Hash modulo 256) a slot v tabulce je zbývající bity hash modulo délky tabulky (tj. Hash děleno délkou 256 modulo tabulky).

Knihovna

Oficiální kód knihovny cdb je veřejná doména: jednotlivé zdrojové soubory jsou takto označeny a jsou k dispozici také ve veřejné doméně djbdns balík. Zbytek balíčku cdb však býval bezlicenční software, což znamená, že musí být distribuován doslovně. Neobvyklé licencování a jednoduchost formátu přiměly ostatní, aby znovu implementovali knihovnu a vydali ji za běžnějších podmínek, jako je knihovna TinyCDB Michaela Tokareva, která je dostupná pod veřejnou doménou.[2]

V roce 2009 byly všechny cdb zveřejněny.[3]

Zejména tvůrce cdb nemá v úmyslu použít cdb jako sdílená knihovna. To se liší od prakticky všech podobných dbm-jako databáze, jako např Berkeley DB.

Reference

  1. ^ Specifikace CDB
  2. ^ „TinyCDB - konstantní databáze“. www.corpit.ru. Citováno 2016-12-12.
  3. ^ „Často kladené otázky od distributorů“.

externí odkazy