B-stromy

Algoritmy Vyhledávání B-stromy

B-stromy jsou jedním z typů datových struktur, konkrétně z vyhledávacích stromů. Od většiny ostatních se však liší v tom, že v jeho uzlech lze uložit více než jeden prvek. Co to s sebou přináší? Pojďme se na to podívat!

Nejdříve si definujeme B-stromy, konkrétně jejich vlastnosti. Pomůže nám to k jednoduššímu pochopení algoritmu :-)

Vlastnosti

  • 1. Maximální počet prvků v uzlu je u všech uzlů stejný a volíme ho na začátku (od této chvíle budu tuto vlastnost nazývat kapacita a značit ji budu písmenem r (r >= 2)). Pojďme si zde rovnou říci, že důležitá je většinou polovina z kapacity. Polovinu (budeme značit p) z r vypočítáme snadno: p=r/2 (v případě sudého r), p=(r-1)/2 (v případě lichého r)
  • 2. Jednotlivé uzly (kořene) musí být aspoň z poloviny zaplněné, nesmí však překročit r.
  • 3. Prvky uložené v uzlu jsou seřazeny vzestupně.
  • 4. Uzel je buďto list anebo má o jednoho následníka více, než je počet prvků v něm uložený. Následník pak v sobě obsahuje prvky větší než jeho levá hodnota v předkovi a menší než pravá hodnota předkovi.
  • 5. Listy jsou v B-stromu jen v jeho poslední (nejspodnější) úrovni. Jinými slovy vzdálenost všech listů od kořene je rovna (a je rovná i s výškou stromu).
B-strom datová struktura

Na obrázku vidíme B-strom o výšce 1 a s kapacitou 3. Jelikož je v jeho kořenu (uzel nahoře) jeden prvek, podle vlastnosti výše musí mít přesně 2 následníky, pokud to tedy není listový uzel. Na druhou stranu, jeho potomci jsou listové uzly, takže musí být na stejné úrovni. Můžete také zkontrolovat, že prvky jsou seřazené, takže všechny vlastnosti platí.

Pozn.: Někdy můžete v souvislosti s B-stromy zaslechnout pojem "řád". B-strom s kapacitou uzlu r má řád r + 1, jelikož nelistový uzel může mít až r + 1 následníků.

Vyhledávání

Nyní k samotnému algoritmu. Kvůli odlišnosti implementace, velikosti a složitosti, zde nebudu uvádět pseudokód nebo kód v nějakém konkrétním jazyce. Ale napíši detailní popis slovy pro vyhledávání, vkládání a odstraňování.

Značení

  • Aktuální uzel budeme označovat u (na začátku jím bude kořen uzlu - nejvyšší uzel, který nemá žádného předka)
  • Hledanou hodnotu poté budeme označovat x.

Algoritmus

1. Vyhledání x v uzlu u (můžeme použít například sekvenční nebo binární vyhledávání), tento krok může skončit 3 způsoby:

  1. x byl v u nalezen - vyhledávání úspěšně končí
  2. x nebyl nalezen v u a u je list - vyhledávání neúspěšně končí
  3. x nebyl v u nalezen a u je nelistový. V tom případě skončilo v místě, kde je odkaz na jeho následníka, který by měl prvek obsahovat. Pokračujeme v tedy v něm, změníme aktuální uzel u na onoho následníka a vrátíme se na krok 1.
Vyhledávání v B-stromu

A to je vše :-) Velice snadné že?

Vkládání prvku

Značení

  • Aktuální uzel - u
  • Přidávaný prvek - x

Algoritmus

1. Provedeme vyhledání ve stromu, může to skončit 2 způsoby:

  1. prvek x byl nalezen. Přidávání končí (nepředpokládá se více stejných prvků ve stromu)
  2. vyhledávání skončilo v listovém uzlu u, kde by měl prvek nalézat (vzhledem k velikosti), x na toto místo vložíme. Pokud uzel u není zaplněn (počet prvků v u není větší než r), přidávání končí. Pokud však r přesáhneme, dojde k rozdělení uzlů.

2. Rozdělujeme uzly. Jestliže má u po přidání r+1 prvků, rozdělíme uzel na tři části. Využijeme známého p a rozdělíme ho tedy:

P prvků na začátku uzlu + prvek uprostřed + p prvků na konci uzlu.

První a druhá část budou nové uzly (můžete si všimnout, podmínka minimálního počtu p bude platit) a prvek uprostřed přesuneme do předchůdce, na místo, kde byl odkaz na uzel u. Jakmile přesuneme prvek, vytvoříme nalevo a napravo od něho odkazy na nově vzniklé listy.

Možná vás napadlo, že jsme tím problém nemuseli vyřešit. Ano, skutečně, v případě umístění prvku výše může dojít k přeplnění uzlu, do kterého jsme prvek vložili. To vyřešíme stejným způsobem. Krok 2 opakujeme dokud se nedostaneme ke kořenu nebo dokud nedojdeme k uzlu, který nebude přeplněn. Když i v kořenu dojde k přeplnění, rozdělí se znovu na tři části a prostřední bude umístěna do samostatného uzlu a tento uzel se stane novým kořenem. Části s p prvky budou znovu jeho odkazy. V této chvíli dochází ke zvětšení stromu.

Zkusme si to na příkladu. Vezměme si například tento strom kapacity 4.

Vkládání prvku do B-stromu – 1

Přidáme prvek 15. To by neměl být problém. Problémem však je, že jsme překročili kapacitu uzlu.

Vkládání prvku do B-stromu – 2

Naštěstí víme jak to vyřešit - rozdělíme si přeplněný uzel a prvek přesuneme nahoru.

Vkládání prvku do B-stromu – 3

Odebírání prvku

Značení

  • Aktuální uzel - u
  • Odebíraný prvek - x

Algoritmus

1. Provedeme vyhledání ve stromu prvku x, může to skončit 3 způsoby:

  1. x nebylo ve stromu nalezeno - operace končí, není co odebrat.
  2. x bylo nalezeno v listovém uzlu (uzel v nejspodnější úrovni). X z uzlu odstraníme. Když je uzel aspoň z poloviny (p) zaplněn, operace končí. Jinak přejdeme ke 2. kroku.
  3. x bylo nalezeno v nelistovém uzlu. X z uzlu odstraníme a na volné místo umístíme buď největší (tedy nejpravější) prvek z levého podstromu (nejpravější list). Anebo nejmenší (tedy nejlevější) prvek v pravém podstromu (nejlevější list). Pokud je ve všech listových uzlech aspoň polovina prvků, operace odebrání končí. Jinak přejdeme ke 2. kroku.

2. Může se stát, že narušíme podmínku - každý uzel musí být aspoň z poloviny (p) zaplněn, má tedy p-1 prvků. Tento stav lze, samozřejmě, řešit. V podstatě máme řešení 2:

Prakticky to budu předvádět na tomto stromu (r = 4)

Mazání prvku z B-stromu – 1
  1. List u má alespoň jednoho sourozence, který obsahuje více než p prvků. Přesuneme do uzlu u prvek z předchůdce a na nově vzniklé místo v předchůdci přesuneme největší (v případě, že soused je vlevo od u) či nejmenší (v případě, že soused je vpravo od u) prvek ze souseda.

Odstraňujeme 15.

Mazání prvku z B-stromu – 2
  1. List u nemá sourozence, kteří mají více než p prvků. Vytvoříme tedy nový list s r prvky z uzlu u + prvek z předchůdce + prvky ze sourozence u.

Odstraňujeme 12.

Mazání prvku z B-stromu – 3

Zde může nastat situace, že v předchůdci znova dojde k tomu, že počet prvků bude p-1. Řeší se to stejně, záleží na sourozencích. Můžeme se tak dostat až ke kořenu, pokud sloučíme uzel s kořenem, ve kterém byl jen jeden prvek, nově vzniklý uzel se stává kořenem.

A nyní ukáži příklad se změnou kořene. Vezmeme si tento strom, který bude mít kapacitu 4 a odstraníme prvek v kořenu - 60.

Mazání prvku z B-stromu – 4

Odstraníme prvek 60 a přesuneme prvek 59 (největší prvek v levém podstromu) na místo v kořeně, mohli bychom přesunout i 62, ale zbytečně by se nám rozbila podmínka, která určuje, že musí být aspoň z poloviny zaplněný.

Mazání prvku z B-stromu – 5

Vidíme, že všechny vlastnosti B stromu platí.

A to je vše :-)

Na závěr pro zájemce uvedu časovou složitost. U vyhledávání složitost závisí jak velké máme r a jakou metodu vyhledávání použijeme v jednotlivých uzlech. Když zvolíme binární vyhledávání, má logaritmickou složitost. Dále musíme započítat procházení uzlů od kořene k listu, zde výška stromu závisí logaritmicky na počtu prvků. Vyhledávání má tedy logaritmickou složitost. Základem přidání a odebrání prvku je vyhledávání a dále (možný) průchod nahoru. Zde je průchod nahoru zas závislý na výšce stromu. Tedy všechny operace mají logaritmickou složitost, která je již docela příjemná :-)


 

  Aktivity (2)

Článek pro vás napsal Petr Valigura
Avatar
Autor se věnuje programování v různých (i funkcionálních) jazycích, nejčastěji však používá .NET a C#. Baví ho zajímavé algoritmy a věci kolem softwaru obecně.

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 


Miniatura
Předchozí článek
AVL strom
Miniatura
Všechny články v sekci
Vyhledávací algoritmy

 

 

Komentáře

Avatar
David Čápka
Tým ITnetwork
Avatar
David Čápka:

Skvělý článek, velmi jednoduše vysvětleno pro normální lidi :) Nechceš tam hodit i nějaký ten zdrojáček, stačí jen v jednom jazyce?

Odpovědět 12. září 9:04
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Valigura
Redaktor
Avatar
Odpovídá na David Čápka
Petr Valigura:

Díky. Jestli je o to zájem, tak ho můžu napsat, jenom to potrvá asi týden, za chvíli začíná škola, takže toho času tolik není a zase nechci to jen zkopírovat z internetu. Každopádně hodím ho tam :)

Odpovědět 12. září 13:21
Občas je to tady dobrá klauniáda...
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Petr Valigura
Martin Dráb:

Když zvolíme binární vyhledávání, má logaritmickou složitost

Tady dost záleží na počtu prvků v uzlu. Binární vyhledávání zase není zrovna efektivní z hlediska cache (protože v podstatě "náhodně" skáče), takže do určitého počtu prvků je lepší primitivní vyhledávání s lineární asymptotickou složitostí (zkoušet prvek po prvku).

zdroják

Na ten se také těším. Mám někde implementaci v Delphi, kterou bych možná mohl poskytnout (už nevím, v jakém je stavu) a ladil jsem to asi tři dny :-).

Odpovědět  +2 12. září 17:34
2 + 2 = 5 for extremely large values of 2
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovědět 12. září 18:24
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Petr Valigura
Redaktor
Avatar
Odpovídá na Martin Dráb
Petr Valigura:

Děkuji za doplnění, máš pravdu, ale toto není článek o binárním vyhledávání :) ... nechtěl jsem se zde tedy věnovat těmto "drobnostem", také bych tady mohl odvodit časovou složitost, ono pro člověka, který se nevyzná ve vyhledávacích stromech může být ještě víc matoucí to jak jsem zjistil, že je to logaritmická složitost. Ale zdálo se mi trošku přehnané psát to dopodrobna (i tak je tam vše co je potřebné včetně příkladů, teda dle mě), každopádně kdyby bylo potřeba klidně tam většinu věcí rozeberu víc. Já jen psal článek pro sebe, tedy co nejsrozumitelnější a v případě potřeby si to dohledám. A jinak tu větu jsem mohl napsat jinak. :)

Jinak člověk, který umí sekvenční a binární vyhledávání ví, že binární se vyplatí od většího počtu :)

(Ano vím, že se zbytečně ostře obhajuji, ale jsem už takový) :D

Odpovědět 12. září 21:39
Občas je to tady dobrá klauniáda...
Avatar
Martin Dráb
Redaktor
Avatar
Odpovídá na Petr Valigura
Martin Dráb:

Však v pohodě. Jen mi přišlo, že bude lepší, když upozorním na tu věc s binárním vyhledáváním (když jsi jej zmínil v článku jako možnost), aby pak lidé nezačali v sebemenším poli vyhledávat binárně :-), to je celé.

Časovou složitost podle mě zdůvodňovat nemusíš; pro běžné použití stačí, že je logaritmická. Kdo se tím bude muset zabývat víc (např. na VŠ), tak jej pořádné odvození také potká (i když u B stromů to je v pohodě, to spíš bude nešťastný nad jinýma datovýma strukturama, kde to taková legrace není).

Odpovědět  +1 12. září 23:06
2 + 2 = 5 for extremely large values of 2
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 6 zpráv z 6.