B⁺-strom

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 7. února 2022; ověření vyžaduje 1 úpravu .

B⁺-tree je datová struktura založená na B-stromu , vyváženém -ary vyhledávacím stromu s proměnným, ale často velkým počtem dětí na uzel. B⁺-strom se skládá z kořene, vnitřních uzlů a listů, kořenem může být list nebo uzel se dvěma nebo více dětmi. $n$

Původně byla struktura určena k ukládání dat pro efektivní vyhledávání v blokově orientovaném úložném prostředí - zejména pro souborové systémy; aplikace je způsobena tím, že na rozdíl od binárních vyhledávacích stromů mají B⁺-stromy velmi vysoký faktor větvení (počet ukazatelů z nadřazeného uzlu na potomky je obvykle řádově 100 nebo více), což snižuje počet I/O operace, které vyžadují hledání prvku ve stromu.

Varianta B⁺-stromu, ve které byly všechny hodnoty uloženy v listových uzlech, byla systematicky přezkoumána v roce 1979 [1] s tím, že takové struktury IBM používá v technologii přístupu k souborům na sálových počítačích VSAM od roku minimálně 1973.

Struktura je široce používána v souborových systémech - NTFS , ReiserFS , NSS , XFS , JFS , ReFS a BFS používají tento typ stromu pro indexování metadat; BeFS také používá B⁺-stromy k ukládání adresářů. Systémy pro správu relačních databází jako DB2 , Informix , Microsoft SQL Server , Oracle Database (od verze 8), Adaptive Server Enterprise a SQLite podporují tento typ stromu pro indexy tabulek. Mezi NoSQL DBMS pracujícími s modelem klíč-hodnota je datová struktura implementována pro přístup k datům v CouchDB , MongoDB (při použití úložného subsystému WiredTiger ) a Tokyo Cabinet .

Popis

B⁺-strom je vyvážený -ary pořadí (nebo stupeň) vyhledávací strom , který splňuje následující vlastnosti: $n$ $t,$

Každý uzel obsahuje alespoň jeden klíč; klíče v každém uzlu jsou seřazeny, kořen obsahuje klíče od do , jakýkoli jiný uzel obsahuje klíče od do ; listy nejsou výjimkou z tohoto pravidla. Zde je parametr stromu, který je alespoň 2 (a obvykle nabývá hodnot od 50 do 2000 v závislosti na velikosti klíče vzhledem k velikosti stránky, která je zase určena velikostí položky obsahu). $jeden$ $2t-1$ ${\textstyle t-1}$ ${\textstyle 2t-1}$ ${\textstyle t}$
Listy nemají potomky; pro všechny ostatní uzly obsahující klíče daný uzel obsahuje potomky. kde: $K_{1},\dots ,K_{n},$ $(n+1)$
- první dítě a všechny jeho potomky obsahují klíče z rozsahu $(-\infty ,K_{1});$
- pro -té dítě a všechny jeho potomky obsahují klíče z intervalu $2 \leqslant i \leqslant n$ $i$ $(K_{i-1},K_{i});$
- $(n+1)$ -th child a všechny jeho potomky obsahují klíče z intervalu $(K_{n},\infty ).$
Hloubka všech listů je stejná.
Listy mají odkaz na souseda, který vám umožňuje rychle procházet stromem ve vzestupném pořadí klíčů, a odkazy na data.

Konstrukce

Vybudování B⁺-stromu může vyžadovat přebudování mezistruktury, to je způsobeno skutečností, že počet klíčů v každém uzlu (kromě kořene) musí být od do kde je stupeň (nebo pořadí) stromu. Když se pokusíte vložit ( )-tý klíč do uzlu, je nutné tento uzel oddělit; ( )-tý klíč, který je umístěn na sousední vrstvě stromu, funguje jako oddělovací klíč vytvořených větví. . Zvláštním případem je rozdělení kořene, protože v tomto případě se zvyšuje počet vrstev stromu. Charakteristickým rysem dělení listu B⁺-stromu je, že je rozdělen na nestejné části. Výsledkem rozdělení vnitřního uzlu nebo kořene jsou uzly se stejným počtem klíčů Rozdělení listu může způsobit "řetězovou reakci" rozdělování uzlů, která končí u kořene. $t$ $2t,$ $t$ $2t+1$ ${\textstyle t+1}$ $k.$

Vlastnosti struktury

V B⁺-stromu je snadno realizovatelná nezávislost programu na struktuře informačního záznamu.
Hledání nutně končí v listu.
Odstranění klíče má tu výhodu, že k vymazání dojde vždy z listu.
Ostatní operace se provádějí podobně jako u B-stromů.
B⁺-stromy vyžadují více paměti k reprezentaci než klasické B-stromy.
B⁺-stromy mají schopnost přistupovat ke klíčům postupně.

Základní operace se strukturou

Hledat

Kořen B⁺-stromu je výchozím bodem pro celý rozsah hodnot, ve kterém je každý vnitřní uzel podintervalem.

Řekněme například, že potřebujeme najít hodnotu klíče v B⁺-stromu. K tomu hledáme listový uzel obsahující hodnotu V každém interním uzlu potřebujeme zjistit, který následující podřízený uzel následovat, vnitřní uzel B⁺-stromu má nejvíce potomků, kde každý z nich představuje samostatný subinterval. Příslušný uzel se vybere vyhledáním v klíčových hodnotách uzlu: $k$ $k.$ $t$

Funkce : search ( k ) return tree_search ( k , root ); Funkce : tree_search ( k , node ) , pokud je uzel list , vrátí uzel ; switch k do case k < k [ 0 ] return tree_search ( k , p [ 0 ]); case k [ i ] ≤ k < k [ i + 1 ] return tree_search ( k , p [ i + 1 ]); case k [ d ] ≤ k return tree_search ( k , p [ d + 1 ]);

(Tento pseudokód předpokládá, že duplikáty jsou ignorovány.)

Přidání

Chcete-li přidat nový klíč nebo nový záznam, musíte nejprve najít uzel, kam je chcete přidat. V tomto případě je algoritmus:

Pokud uzel není zcela vyplněn (počet prvků po vložení není větší než ), pak přidejte klíč (záznam). $2t-1,$
V opačném případě musíte uzel rozdělit:
- vytvořte nový uzel a poté přesuňte polovinu prvků z aktuálního do nového;
- přidat nejmenší klíč z nového uzlu a adresu k němu (uzlu) k nadřazenému;
- pokud je nadřazený uzel plný, rozdělte jej podobně:
  - přidat prostřední klíč k nadřazenému uzlu;
- opakujte, dokud nadřazený uzel nepotřebuje rozdělení.
Pokud se kořen rozdělí, vytvořte nový kořenový adresář s jedním klíčem a dvěma ukazateli (klíč, který je přidán do kořenového adresáře, je odstraněn z jeho uzlu)

B-stromy se na rozdíl od B⁺-stromů rozšiřují ze strany kořene, nikoli listů.

Odstranění

Chcete-li odstranit klíč nebo položku, musíte nejprve najít listový uzel, ve kterém se nachází. Algoritmus pro odstranění z listového uzlu:

Pokud je uzel alespoň z poloviny plný, algoritmus se ukončí;
Pokud má uzel méně prvků, pak:
- pokus o redistribuci prvků, to znamená přidání prvku z „bratra“ do uzlu - prvku se společným předkem.
- pokud se přerozdělení nezdaří, sloučte uzel s "bratrem".
Pokud dojde ke sloučení, odeberte klíč nebo položku, která ukazuje na vzdálený uzel nebo jeho "sourozence" z nadřazeného uzlu.

Spojení se může rozšířit až ke kořeni, v takovém případě se výška stromu sníží.

Výpočetní složitost operací

Výpočetní složitost každé operace v nejhorším případě: kde je pořadí stromu nebo faktor větvení; je počet prvků ve stromu větví v uzlech stromu. $O(\log {\frac {t}{2n)))$ $t$ $n$

Poznámky

↑ Douglas Comer. Všudypřítomný B-strom // ACM Computing Surveys. - 1979. - Červen ( roč. 11 , č. 2 ). - str. 121-137 . — ISSN 0360-0300 . Archivováno z originálu 17. listopadu 2015.

Literatura

Zubov V. S., Shevchenko I. V. Kapitola 6. Vyhledávání v nebinárních stromech - B-stromy // Struktury a metody zpracování dat. Workshop v prostředí Delphi. - Filin, 2004. - S. 144-164. — ISBN 5-9216-0053-9 .
Donald Knuth . 4. Generování všech stromů. Historie kombinatorické generace // The Art of Programming = The Art of Computer Programming. - M. : "Williams" , 2007. - V. 4. - S. 160. - ISBN 0-321-33570-8 .

Odkazy

B⁺ Tree Visualizer - B+ Tree Visualization

Strom (datová struktura)
Binární vyhledávací strom Strom (teorie grafů) stromová struktura
Binární stromy	binární strom T-strom
Samovyrovnávací binární stromy	AA strom strom AVL Červeno-černý strom Rozvětvený strom strom s pokutami karteziánský strom Fibonacciho strom B-strom T-strom
B-stromy	2-3-strom B⁺-strom B*-strom B x -strom UB strom 2-3-4 strom (a,b)-strom tančící strom
předponové stromy	příponový strom Komprimovaný strom předpon Ternární vyhledávací strom
Binární dělení prostoru	k-rozměrný strom VP strom
Nebinární stromy	Čtyřstrom oktree Řídký Voxel Octree exponenciální strom PQ strom
Rozbití prostoru	R-strom Hilbertův R-strom R+-strom R*-strom X-strom M-strom Fenwickův strom Segmentový strom
Jiné stromy	halda hash tree prstový strom metrický strom Potahový strom BK-strom Dvouřetězový strom iVzdálenost Link-cut strom LSM strom
Algoritmy	Šířka první hledání Hloubka první hledání Algoritmus DSW protokol spanning tree