B+ Tree je rozšírením B stromu, ktoré umožňuje efektívne operácie vkladania, vymazávania a vyhľadávania.
V strome B môžu byť kľúče a záznamy uložené vo vnútorných aj listových uzloch. Zatiaľ čo v B+ strome môžu byť záznamy (údaje) uložené iba na listových uzloch, zatiaľ čo interné uzly môžu ukladať iba kľúčové hodnoty.
Listové uzly stromu B+ sú navzájom prepojené vo forme samostatne prepojených zoznamov, aby boli vyhľadávacie dopyty efektívnejšie.
B+ Tree sa používa na ukladanie veľkého množstva údajov, ktoré nie je možné uložiť do hlavnej pamäte. Vzhľadom na to, že veľkosť hlavnej pamäte je vždy obmedzená, interné uzly (kľúče pre prístup k záznamom) stromu B+ sú uložené v hlavnej pamäti, zatiaľ čo listové uzly sú uložené v sekundárnej pamäti.
veľa štastia
Vnútorné uzly B+ stromu sa často nazývajú indexové uzly. B+ strom rádu 3 je znázornený na nasledujúcom obrázku.
Výhody stromu B+
- Záznamy je možné získať rovnakým počtom prístupov na disk.
- Výška stromu zostáva vyrovnaná a menšia v porovnaní so stromom B.
- K údajom uloženým v B+ strome môžeme pristupovať sekvenčne aj priamo.
- Na indexovanie sa používajú kľúče.
- Rýchlejšie vyhľadávacie dopyty, pretože údaje sú uložené iba na listových uzloch.
Strom B VS Strom B+
| SN | B strom | Strom B+ |
|---|---|---|
| 1 | Tlačidlá vyhľadávania nie je možné opakovane ukladať. | Môžu byť prítomné nadbytočné vyhľadávacie kľúče. |
| 2 | Dáta môžu byť uložené v listových uzloch aj vo vnútorných uzloch | Dáta môžu byť uložené iba na listových uzloch. |
| 3 | Vyhľadávanie niektorých údajov je pomalší proces, pretože údaje možno nájsť na interných uzloch, ako aj na listových uzloch. | Vyhľadávanie je porovnateľne rýchlejšie, pretože údaje možno nájsť iba na listových uzloch. |
| 4 | Odstránenie vnútorných uzlov je také komplikované a časovo náročné. | Odstránenie nikdy nebude zložitý proces, pretože prvok bude vždy odstránený z koncových uzlov. |
| 5 | Uzly listov nie je možné prepojiť. | Uzly listov sú navzájom prepojené, aby boli operácie vyhľadávania efektívnejšie. |
Vloženie do stromu B+
Krok 1: Vložte nový uzol ako listový uzol
Krok 2: Ak list nemá požadovaný priestor, rozdeľte uzol a skopírujte stredný uzol do ďalšieho indexového uzla.
Krok 3: Ak uzol indexu nemá požadovaný priestor, rozdeľte uzol a skopírujte stredný prvok na ďalšiu stránku indexu.
Príklad:
Vložte hodnotu 195 do B+ stromu rádu 5 znázorneného na nasledujúcom obrázku.
css zarovnávanie obrázkov
195 sa vloží do pravého podstromu 120 za 190. Vložte ho na požadované miesto.
Uzol obsahuje väčší ako maximálny počet prvkov, teda 4, preto ho rozdeľte a stredný uzol umiestnite k rodičovi.
význam xd
Teraz indexový uzol obsahuje 6 potomkov a 5 kľúčov, čo porušuje vlastnosti stromu B+, preto ho musíme rozdeliť, ako je znázornené nasledovne.
Odstránenie v strome B+
Krok 1: Odstráňte kľúč a údaje z listov.
Krok 2: ak listový uzol obsahuje menej ako minimálny počet prvkov, zlúčte uzol s jeho súrodencom a odstráňte kľúč medzi nimi.
Krok 3: ak indexový uzol obsahuje menej ako minimálny počet prvkov, zlúčte uzol so súrodencom a presuňte kľúč nadol medzi nimi.
Príklad
Vymažte kľúč 200 zo stromu B+ znázorneného na nasledujúcom obrázku.
200 sa nachádza v pravom podstrome 190, po 195. vymažte ho.
Zlúčte dva uzly pomocou 195, 190, 154 a 129.
Teraz je prvok 120 jediný prvok prítomný v uzle, ktorý porušuje vlastnosti stromu B+. Preto ho musíme zlúčiť pomocou 60, 78, 108 a 120.
Teraz sa výška stromu B+ zníži o 1.
previesť java objekt na json
