B+Tree v PHP — jakubův notes – programování a vejšplechty

Když jsem konečně rozchodil metatable, byl to prakticky tantrický okamžik. Och, ono to vážně funguje! A ukládá! A vybírá! Jako když malé děcko dostane lízátko. Navíc, já jsem si to lízátko sám i udělal.

Ale neusnul jsem takříkajíc na vavřínech a šel jsem ještě dál. Když si vezmete snad jakoukoli databázi, tak najdete B+Tree, další B+Tree a ještě více B+Tree. Inu, proč se neinspirovat a neudělat taky takový B+Tree? Samozřejmě zcela v PHP.

A tak vznikla třída btree, která umí spravovat B+Tree uložený v souboru. API je opět minimalistické a bude vám stačit osvojit si jen pár metod – v případě btree si vystačíte s polovinou metod než u metatable (celkem tedy se třemi). Okolo metatable jsem udělal velký humbuk, u btree se spokojím s oznámením tady na blogu.

GitHub jsem si docela oblíbil, takže opět můžete zdrojový kód získat z repozitáře právě tam:

$ git clone git://github.com/jakubkulhan/btree.git

Nejdříve ze všeho je potřeba si vytvořit instanci. Zase je tu statická metoda open():

$btree = btree::open('my.tree');

Klasicky (alias stejně jako u metatable), pokud vše proběhlo v pořádku, open() vrátí novou instanci btree, jinak FALSE. Proč všude cpeš „oupn“ metodu? Samozřejmě by šlo nechat konstruktor jako public a v případě nějaké chyby vyhodit výjimku. Avšak nemohu si pomoci – výjimky prostě nemám rád. Objekty jsou naprosto skvělé, dokonce i do Céčka (takový ten dřevní jazyk; jen pro fajnšmekry) přenáším některé své návyky z OOP. Ale výjimky? Dílo ďáblovo! Hlavně, když dělají něco, co by člověk nečekal.

Když už jeden má instanci btree, bylo by záhodno si do stromu něco uložit:

$btree->set('key', 'value');

(Opravdu jsem nepřišel na chytřejší název metody.) Narozdíl od metatable může jít jako druhý argument, jako hodnota, cokoli, co se dá serializovat, a ne jen určité typy. Ale stejně jako je tomu u metatable, vymazání určitého klíče se provádí přiřazením NULL:

$btree->set('key', NULL);

Pro získání je jako u metatable metoda get():

assert($btree->get('key') === 'value');

Tohle je všechno, co budete potřebovat, budete-li chtít použít B+Tree. Minimalistická API, to je moje.

U metatable jste se museli starat o uzavírání – buď předáním flagu AUTOCLOSE při otevírání nebo ručně. U btree tomu tak není, protože veškeré úpravy stromu probíhají append-only – tzn. že se nikdy nepřepisují již zapsaná data. Má to hodně výhod. Nemusíte se bát, že by se data nějak poškodila. Prakticky nejsou potřeba zámky (bohužel jsem nevymyslel, jak udělat set() bez zamykání; ale zatímco jedna instance zapisuje, můžete stále v klidu číst pomocí get()). A také to znamenalo velké zjednodušení kódu oproti metatable, kde k zajištění konzistence dat se všechno muselo kopírovat do *~handle souboru.

Co se tedy stane, pokud např. v prostředku zápisu nějakých dat btree vypadne elektřina? Nepůjde to vysvětlit bez toho, abych popsal formát souboru.

Jelikož strom se skládá z jednotlivých uzlů, tak i soubor se musí skládat z uzlů. Navíc se uzly do souboru musí ukládat „ploše“, jelikož soubor je jako jeden dlouhý řetězec jedniček a nul. Každý uzel v souboru je reprezentován jako 32-bitové bezznaménkové číslo (formát N pro pack()) následované počtem bytů uložených právě v tom čísle. První dva byty určují typ uzlu a pak je serializovaná podoba uzlu.

Jsou pouze dva typy uzlů – kp a kv. První typ – kp (key-pointer) – je asociativní pole obsahující dvojice (klíč, ukazatel), kde ukazatel je integer ukazující na jiný uzel (offset uzlu v souboru). Druhý – kv (key-value) – je vždy listem stromu a obsahuje již dvojice (klíč, hodnota). Nebudu nic zapírat, inspirací pro mě byla CouchDB.

CouchDB B+Tree (reduce hodnot si nevšímejte, tohle má CouchDB kvůli pohledům a btree žádné pohledy nemá)

„Vždy“ na konci souboru je ukazatel na kořen stromu následovaný „hlavičkou“ sestávající z řetězce "\xffbtree" (\xff je byte plný samých jedniček).

Řekněme tedy, že ukládáme nějakou hodnotu. Jak se tomu u B+Tree dělá, traverzujeme stromem až do listu (kv uzlu), kam by hodnota měla být uložena. Udělá se vše potřebné (rozdělování/slučování uzlů) a postupně se všechny ovlivněné uzly zapisují do souboru – připojují na konec. Na závěr je připojena nová poloha kořene s novou hlavičkou a je vynucen zápis na disk. Když se kdykoli od začátku zápisu do doby, než je všechno úspěšně na disku, něco stane, btree si z toho nic nedělá: Je zapsána třeba jen polovina uzlů? Chybí hlavička? To mě nerozhází!

Při hledání kořene se totiž ověřuje, jestli je na konci souboru opravdu celá hlavička, a pokud ne, btree se od konce souboru dobírá k poslední úspěšně zapsané hlavičce. (Pozor tedy – uložením řetězce "\xffbtree" můžete btree pěkně pomotat hlavu!) To je celé kouzlo. Žádné opravovací algoritmy, nebo žurnály nejsou potřeba, protože i když je soubor „rozbitý“ nedokončeným zápisem, strom je v posledním konzistentním stavu. Všechna data, na která není odkazováno, jsou považována za „neexistující“.