Klíčový rozdíl: V počítačích jsou binární stromy stromové datové struktury, které ukládají data, a umožňují uživateli přístup, vyhledávání, vkládání a odstraňování dat v algoritmickém čase. Rozdíl mezi stromy B a B + spočívá v tom, že v B-stromu mohou být klíče a data uloženy jak v interních, tak v listových uzlech, zatímco ve stromu B + mohou být data a klíče uloženy pouze v uzlech listů .
Binární stromy jsou vyvážené vyhledávací stromy, které jsou navrženy tak, aby dobře fungovaly na zařízení pro sekundární ukládání s přímým přístupem, jako jsou magnetické disky. Rudolf Bayer a Ed McCreight vynalezli koncept B-stromu.
B-strom je obecný binární vyhledávací strom, ve kterém může každý uzel mít více než dvě děti. Každý vnitřní uzel ve stromu B obsahuje několik klíčů. Tyto klíče oddělují hodnoty a dále vytvářejí vedlejší stromy. Vnitřní uzly ve stromu B mohou mít proměnné počty podřízených uzlů, které jsou uspořádány v předem definovaném rozsahu. V okamžiku, kdy jsou nějaká data vložena nebo odebrána z libovolného uzlu, dochází ke změně počtu podřízených uzlů. K udržení předdefinovaného rozsahu mohou být interní uzly spojeny nebo rozděleny. Ve stromu B je povolen rozsah dětských uzlů, kvůli kterým je třeba zachovat předdefinovaný rozsah.
Stromy B nemusejí být často vyvažovány na rozdíl od ostatních vyhledávacích stromů s vlastním vyvažováním. Uzly v těchto stromech nejsou vždy plné; Proto jsou prostory v těchto stromech zbytečně zbytečné, což vede k plýtvání prostorem. Pouze dolní a horní hranice počtu podřízených uzlů jsou obvykle určeny pro konkrétní implementaci. Například ve stromu 2-3 B (často jednoduše označován jako strom 2-3), každý vnitřní uzel může mít pouze 2 nebo 3 podřízené uzly.
Kromě toho je strom B optimalizován pro systémy, které čte a zapisují velké bloky dat. To se běžně používá v databázích a souborových systémech. Ve stromu B jsou všechny uzly udržovány ve stejné vyrovnávací hloubce od kořenových uzlů. Tyto hloubky se pomalu zvyšují, jak se zvyšuje počet prvků; to má za následek, že všechny listové uzly jsou ještě jeden uzel vzdálenější od kořene. Kromě toho jsou B-stromy výhodnější ve srovnání s jinými implementacemi, pokud jde o čas potřebný pro přístup k datům.
Strom B + je strom n-array s uzlem, který se skládá z velkého počtu dětí na uzel. Kořenem může být list nebo uzel, který obsahuje více než dvě děti. Strom B + se skládá z kořenů, vnitřních uzlů a listů.
Strom B + je stejný jako strom B; jediný rozdíl spočívá v tom, že v stromu B + je v dolní části doplněná přidaná hladina s připojenými listy. Také, na rozdíl od stromu B, každý uzel ve stromu B + obsahuje pouze klíče a ne páry klíč-hodnota.
Navíc vyrovnávací faktor nebo pořadí stromu B + měří kapacitu pro vnitřní uzly ve stromu, tj. Počet uzlů, které mohou mít. Skutečný počet dětí pro uzel je omezen na vnitřní uzly. Kořen je výjimkou, jelikož je povoleno mít více než dva děti. Například pokud je pořadí stromu B + 7, každý interní uzel (kromě root) může mít mezi 4 a 7 dětmi; zatímco kořen může mít mezi 2 a 7. Primární hodnota stromu B + spočívá v ukládání dat pro efektivní načítání v kontextu úložiště orientovaném na blok a zejména v souborových systémech.
Primární hodnota stromu B + spočívá v ukládání a udržování dat, takže data nejsou ztracena. Tento přístup se používá zejména v kontextu úložiště orientovaném na bloky a v některých konkrétních souborových systémech. Listy, které jsou nejdůležitějšími indexovými bloky stromu B +, jsou často navzájem propojeny v propojeném seznamu; a tím se zjednodušují a zjednodušují rozsahové dotazy nebo uspořádaná iterace prostřednictvím bloků. Dále prostorový faktor není promarněn stromy B +. Strom B + poskytuje efektivní formát datové struktury bydlení, což zjednodušuje jejich přístup a ukládání. Stromy B + jsou obzvláště užitečné jako index databázového systému, kde jsou data obvykle umístěna na disku.
Srovnání stromu B a stromu B +:
B Strom | Strom B + | |
Krátké popisy webových stránek | AB strom je organizační struktura pro ukládání a vyhledávání informací ve formě stromu, ve kterém jsou všechny terminálové uzly ve stejné vzdálenosti od základny a všechny neterminární uzly mají mezi n a 2 n sub stromy nebo ukazatele (kde n je celé číslo). | Strom B + je strom n-array s proměnnou, ale často velkým počtem dětí na uzel. Strom B + se skládá z kořenů, vnitřních uzlů a listů. Kořenem může být buď list nebo uzel se dvěma nebo více dětmi. |
Také známý jako | Vyvážený strom. | B plus strom. |
Prostor | Na) | Na) |
Vyhledávání | O (log n) | O (log bn) |
Vložit | O (log n) | O (log bn) |
Odstranit | O (log n) | O (log bn) |
Úložný prostor | V stromu B vyhledá klávesy a data uložená v interních nebo listových uzlech. | Ve stromu B + data uložená pouze v uzlech listů. |
Data | Uzly listů tří ukazatelů ukládání do záznamů spíše než skutečné záznamy. | Uzly listu stromu ukládají do záznamů skutečný záznam namísto ukazatelů. |
Prostor | Tyto stromy plýtvají prostorem | Tam stromy neztrácejí prostor. |
Funkce uzlů listů | V stromu B nemůže list uzlu ukládat pomocí propojeného seznamu. | Ve stromu B + jsou data uzlových uzlů uspořádána v sekvenčním propojeném seznamu. |
Hledání | Zde se vyhledávání v B-stromu stává obtížným, jelikož data nejsou nalezena v uzlu listů. | Zde je vyhledávání všech dat ve stromu B + velmi snadné, protože všechny data se nacházejí v uzlech listů. |
Vyhledávací přístup | Zde ve stromu B není vyhledávání snadné ve srovnání s stromem B +. | Tady ve stromu B + je vyhledávání snadné. |
Redundantní klíč | Neuvádí redundantní vyhledávací klíč. | Uchovávají redundantní vyhledávací klíč. |
Aplikace | Jsou to starší verze a nejsou tak výhodné ve srovnání s stromy B +. | Mnoho implementátorů databázových systémů dává přednost strukturální jednoduchosti stromu B +. |
