Stromy pat°φ k nejobvyklejÜφm metodßm organizace dat na vn∞jÜφch pam∞tech s p°φm²m p°φstupem, proto₧e umo₧≥ujφ asociativnφ p°φstup i sekvenΦnφ zpracovßnφ dat podle vzestupnΘho (nebo sestupnΘho) uspo°ßdßnφ klφΦ∙. P°edstavujφ tedy zp∙sob implementace indexu. Na jejich statickΘ verzi byly zalo₧eny ji₧ prvnφ implementace indexsekvenΦnφ metody v 60. letech. Dynamickou stromovou strukturou byl historick² produkt IBM VSAM, jeÜt∞ p°ed objevem B-strom∙, na stromech byly ji₧ v polovin∞ 60. let zalo₧eny datovΘ struktury dnes vÜeobecn∞ znßmΘho relaΦnφho S╪BD ADABAS.

Vzhledem k charakteristick²m vlastnostem vn∞jÜφch pam∞tφ jsou uzly stromu tvo°eny strßnkami (obvykle pevnΘ dΘlky), do nich₧ se sna₧φme umφstit co nejvφce dat. Tato data budou tvo°ena zßznamy, podobn∞ jako u klasickΘho indexu, tj. < klφΦ, adresa> , kde klφΦ je hodnota atributu, podle kterΘho indexujeme a adresa ukazuje na uzel-nßslednφk ve strom∞, p°φpadn∞ na seznam adres zßznam∙, nebo p°φmo do primßrnφho souboru (Φi databßzovΘ tabulky).

Idea je jednoduchß. Lze vyjφt nap°. z binßrnφch vyhledßvacφch strom∙ (BVS), kde mno₧ina klφΦ∙, nap°. p°irozen²ch Φφsel, je umφst∞na do uzl∙ stromu tak, ₧e je zachovßno uspo°ßdßnφ Φφsel. Na obr. 1 je ukßzka takovΘho stromu. Hledßme-li nap°. klφΦ 7, postupuje se z ko°ene stromu levou cestou, pak pravou, tj. ve 3. kroku je klφΦ nalezen.

9 š

6 š š 11

2 š 7 š Obr. 1 Binßrnφ vyhledßvacφ strom

Vyu₧φt BVS pro indexovßnφ relacφ p°φmo nelze, proto₧e nenφ jednoduÜe zobraziteln² do strßnek na disku. Navφc, pro velkou mno₧inu klφΦ∙, je stßle moc hlubok². Nap°. pro 524 288 (tj. 2¹⁹) by m∞l v lepÜφm p°φpad∞ takov² strom hloubku log₂524 288, tj. 19, a to by p°i nevhodnΘ organizaci na disku mohlo znamenat p°φliÜ mnoho Φtenφ strßnek do vnit°nφ pam∞ti.

ProblΘm vy°eÜil v r. 1972 Φlßnek ôOrganization and maintenance of large ordered indicesö o B-stromech pßn∙ Bayera a McCrighta v Φasopise Acta Informatica. èlo zase o hezk² p°φklad ovlivn∞nφ teorie praxφ. B-stromy toti₧ byly vyvinuty p°i °eÜenφ praktickΘho problΘmu - uspo°ßdßnφ souΦßstek v rßmci informaΦnφho systΘmu Boeing Company. MyÜlenka jejich tv∙rc∙ spoΦφvala na zobecn∞nφ BVS, tj. pou₧il se m-ßrnφ strom, kde ka₧d² uzel mß nejv²Üe m nßslednφk∙. Budeme dßle pro zjednoduÜenφ p°edpoklßdat, ₧e m je sudΘ. Proto₧e variant definici B-strom∙ je vφce, uvedeme zde tu, kterß se vyskytuje v relaΦnφch S╪BD pro implementaci indexu nejΦast∞ji.

B-strom (°ßdu m) je m-ßrnφ strom, spl≥ujφcφ nßsledujφcφ omezenφ:

• Ko°en mß nejmΘn∞ dva potomky, pokud nenφ listem,
• ka₧d² uzel krom∞ ko°ene a listu mß nejmΘn∞ m/2 a nejv²Üe m potomk∙,
• ka₧d² uzel mß nejmΘn∞ m/2 -1 a nejvφce m-1 datov²ch zßznam∙ (v∞tÜinou pouze klφΦ∙),
• vÜechny v∞tve od ko°ene do listu jsou stejn∞ dlouhΘ,
• data v nelistovΘm uzlu jsou organizovßna nßsledovn∞:

p₀,(k₁,p₁),(k₂,p₂),...,(k_n,p_n),u

kde p₀,p₁,...,p_n jsou ukazatele na potomky, k₁,k₂,...,k_n jsou klφΦe, u je nevyu₧it² prostor a zßznamy (k_i,p_i) jsou uspo°ßdßny vzestupn∞ podle klφΦ∙, p°iΦem₧ m/2 -1 £ n £ m-1.

• odpovφdß-li ukazateli p_i, kde i Î <1,n>, podstrom U(p_i), potom platφ:

(i) pro ka₧dΘ k v U(p_i-1) je k £ k _i,

(ii) pro ka₧dΘ k v U(p_i) je k > k _i,

• listy obsahujφ ·plnou mno₧inu klφΦ∙.

Z (i) plyne, ₧e klφΦe ve vnit°nφch uzlech B-stromu jsou pouze rozhodovacφ, podstatnß je existence klφΦe v listovΘm uzlu. Ukazatele p_i v listech ji₧ ukazujφ do primßrnφho souboru nebo na seznamy ukazatel∙ apod. Spokojme se s tφm, ₧e jde o implementaΦn∞ zßvislou Φßst definice B-stromu.

Na obrßzku 2 je B-strom s m=3, do jeho₧ uzlu lze umφstit jeden a₧ dva klφΦe, z vnit°nφho uzlu se lze dostat dvou a₧ t°ech podstrom∙. V grafickΘm vyjßd°enφ existuje jeÜt∞ mφsto pro t°etφ klφΦ, co₧ nenφ v souladu s definicφ. M∙₧eme si je vÜak interpretovat jako nevyu₧itΘ mφsto u z definice B-stromu. Uzly jsou oΦφslovßny p°irozen²mi Φφsly (adresy strßnek), ukazatele Zi v listech ukazujφ na datovΘ struktury mimo B-strom.

6

Karla - -

2 5 -

2 5

F.L .V∞k - - Matka - -

0 4 - 3 1 -

0 4

BabiΦka F.L.V∞k - Karla - -

Z3 Z5 - Z1 - -

3 1

Matka - - Poklad Pustina -

Z0 - - Z2 Z4

Obr. 2 B-strom

Samotnß struktura B-stromu ovÜem nenφ to nejpodstatn∞jÜφ. Ke struktu°e pat°φ algoritmy operacφ INSERT a DELETE, kterΘ podporujφ to, Φemu °φkßme dynamika struktury. Algoritmy jsou stav∞ny tak, ₧e struktura se ôzv∞tÜujeö s poΦtem p°ib²vajφcφch klφΦ∙, Φi ôzmenÜujeö s poΦtem ub²vajφcφch klφΦ∙. D∙le₧it²m pojmem zde je Üt∞penφ, resp. slΘvßnφ strßnek. Na obrßzku 3 a) je ukßzßna situace p°ed provedenφm operace INSERT(BabiΦka), na 3 b) situace potΘ.

2

Matka - - a) p°ed INSERT(BabiΦka)

0 1 - -

0 1

Karla Matka - Poklad - -

Z1 Z0 - Z2 - -

2

Karla Matka - b) po INSERT(BabiΦka)

0 3 1

0 3 1

BabiΦka Karla - Matka - - Poklad

Z3 Z1 - Z0 - - Z2

Obr. 3 Vklßdßnφ do B-stromu

Algoritmus INSERT hledß mφsto (listov² uzel), kam pat°φ vklßdan² klφΦ a v p°φpad∞, ₧e je uzel obsazen, Üt∞pφ strßnku, tj. starou nahrazuje dvojicφ (starß, novß). Polovina klφΦ∙ starΘ strßnky jde do starΘ, polovina do novΘ, dßle se ob∞ strßnky musφ p°ipojit do uzlu-p°edch∙dce. To znamenß dalÜφ vklßdßnφ klφΦe a event. dalÜφ Üt∞penφ.

Bylo dokßzßno, ₧e tφmto zp∙sobem se uzly obsadφ v pr∙m∞ru ze 69%, tj. je t°eba pamatovat, ₧e v B-stromech se trochu h²°φ mφstem. V²hoda je vÜak v malΘm poΦtu p°φstup∙ na disk. Lze si snadno spoΦφtat, ₧e p°i velikosti m °ßdov∞ stovky bude mφt B-strom v pr∙m∞rnΘ aplikaci hloubku 2-3.

O B-stromech by se toho dalo °φci jeÜt∞ moc. Lze jim nap°. provßzat listy ukazateli, co₧ vede k tzv. B⁺-strom∙m. Umo₧≥ujφ zφskat snadno sekvenci zßznam∙ uspo°ßdanou dle danΘho klφΦe, ani₧ by se prolΘzal cel² B-strom. Zßv∞rem snad u₧ jen jedno. Co znamenß to B? Auto°i tvrdφ, ₧e je to od ôBalancedö (vyvß₧en²). N∞kte°φ se domnφvajφ, ₧e se tφm zv∞Φnil jeden z autor∙. Jedno je vÜak jistΘ: s ôBinaryö (jak se obΦas n∞kdo naivn∞ myslφ) to nemß nic spoleΦnΘho.