B-stromy

Algoritmy Vyhledávání B-stromy

ONEbit hosting Unicorn College Tento obsah je dostupný zdarma v rámci projektu IT lidem. Vydávání, hosting a aktualizace umožňují jeho sponzoři.

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
Zobrazit starší komentáře (3)

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

Klidně to sem hoď :)

Odpovědět 12.9.2016 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
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.9.2016 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.9.2016 23:06
2 + 2 = 5 for extremely large values of 2
Avatar
Fleury#93
Člen
Avatar
Fleury#93:

Pěkné srozumitelné, ale co takhle uvést citace na články ze, kterých si čerpal znalosti či se nějakým způsobem inspiroval :)

 
Odpovědět 25. ledna 11:48
Avatar
Petr Valigura
Redaktor
Avatar
Odpovídá na Fleury#93
Petr Valigura:

Díky, čerpal jsem ze svého studia na vysoké škole :) žádnou konkrétní stránku jsem nepoužil. Tedy psal jsem to z hlavy, ze znalostí, které jsem nasbíral na VŠ a z několika (desítek) článků, které jsem přečetl, když jsem se učil na zkoušku. Kdybych tu měl psát přímé citace či zdroje musel bych si vyloženě vymýšlet. U většiny ostatních článků zde na itnetworku se také neuvádějí citace (dle mého) právě z toho důvodu, že to jsou originály autorů, kteří danou věc umí a chtějí ji předat dál. Články zde nevznikají tak, že se autor jen tak z nudy rozhodne, že napíše o problematice (kterou téměř neovládá) otevře si dvě stránky a z každé zkopíruje část. :)

Odpovědět 25. ledna 13:48
Občas je to tady dobrá klauniáda...
Avatar
Fleury#93
Člen
Avatar
Odpovídá na Petr Valigura
Fleury#93:

No třeba ty příklady nejsou úplně z tvojí hlavy, změnit čísla dokáže každý. Citovat je slušnost, která navíc může posloužit taky k doplnění ostatních večí z dané problematiky.

 
Odpovědět 25. ledna 14:17
Avatar
Petr Valigura
Redaktor
Avatar
Odpovídá na Fleury#93
Petr Valigura:

Nevím o co ti úplně jde... jestli je tohle tvoje forma zábavy - chodit kolem horké kaše a nenapsat rovnou co se ti na tom nezdá... Příklady jsem vymýšlel tímto způsobem - Chtěl jsem nějaký krátký příklad, ve kterém bych ukázal to co je zrovna třeba - prošel jsem si svoje zápisky (které se skládaly z různých cvičení, zkušebních testů, příklady ze stránek atd.) jestli nenarazím na nějaký pěkný příklad, na kterém bych to mohl ukázat, když jsem narazil, udělal jsem typově podobný, když jsem nenarazil, tak jsem si ho vymyslel.

Jestli máš, ještě nějaké přímé dotazy (nebudu z tebe páčit co máš na srdci), rád ti na ně odpovím v soukromé zprávě, nemá cenu aby jsme to tady spamovali. :)

Odpovědět  +1 25. ledna 16:25
Občas je to tady dobrá klauniáda...
Avatar
Fleury#93
Člen
Avatar
Fleury#93:

Tak jde mě o to, že bysme mohli tady na síti citovat, nic víc (viz můj předochzí příspěvek). Nejde mě o žádné trollení.

 
Odpovědět 25. ledna 16:34
Avatar
Petr Valigura
Redaktor
Avatar
Odpovídá na Fleury#93
Petr Valigura:

Teď už to zavání off topicem, takže na toto téma je to ode mě poslední odpověď tady :)
Zdá se ti, že tady na síti by se mělo více citovat? Skvělé vytvoř tady na fóru příspěvek s tím, že se ti nelíbí, že se tu necituje nebo napiš lidem co schvalují články.

Zdá se ti, že jsem okopíroval nějaký článek? Pošli mi ten článek a prodiskutujeme to.

Ano nenarodil jsem s touto znalostí ani jsem to nevymyslel a skutečně jsem při svém učení použil články na internetu, ale už ne při vypracování tohoto článku. Jak jsem říkal to co jsem použil byly moje zápisy, hlavně tedy příklady, ono když chceš aby ten strom nebyl moc vysoký tak těch příkladů tolik nevymyslíš - téměř pokaždé najdeš nějaký strom, který je tomu tvému podobný ať už čísly, nebo uzly.

P.S.: Pokud opravdu existuje nějaký článek, který je téměř totožný, má stejné příklady a jen změněná čísla, pošli mi ho, ačkoliv mé svědomí je čisté, sám bych se nerad prezentoval, tak že kradu články. A tento článek bych zeditoval :)

Odpovědět 25. ledna 17:03
Občas je to tady dobrá klauniáda...
Avatar
Fleury#93
Člen
Avatar
Odpovídá na Petr Valigura
Fleury#93:

No možná ani né tak citace jako min. seznam literatury by byl vhodný.

 
Odpovědět 25. ledna 17:15
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 10 zpráv z 13. Zobrazit vše