Б+ стабло

У рачунарству, Б+ стабло је тип стабла који представља ускладиштене податке на начин који омогућава ефикасно уметање, проналажење и брисање елемената, од којих сваки има идентификатор, кључ. То је динамички индекс у више нивоа који има ограничен максимум и минимум кључева у сваком сегменту индекса (који се назива блоком). Код Б+ стабла, за разлику од Б-стабла, сви подаци се складиште у листовима; само кључеви се складиште у унутрашњим чворовима.

Првенствена предност Б+ стабала је складиштење података на начин који омогућава ефикасно проналажење. Подаци се чувају у блоковима. Ефикасност Б+ стабала првенствено потиче из чињенице да за разлику од бинарног стабла претраге оно има врло велику разгранатост (енгл. fanout), обично реда 100 или више, што умањује број улазно/излазних операција неопходних да би се пронашао елемент у стаблу.

Фајлсистеми NTFS, ReiserFS, NSS, XFS, и JFS користе овај тип стабала за индексирање метаподатака. Системи за управљање базама података као што су PostgreSQL и MySQL такође често користе овај тип стабла за индексе табела.

Детаљи

Ред Б+ стабла је мера капацитета његових чворова (то јест броја синова неког чвора) Дефинише се као број d такав да $\lceil d/2\rceil \leq m\leq d$, где је m број синова сваког чвора. На пример, ако је ред Б+ стабла 7, сваки унутрашњи чвор може да има између 4 и 7 синова. Корен може да их има између 2 и 7.

Претрага

Алгоритам који обавља претрагу за уносом r преко показивача прати путању до одговарајућег листа (у коме би требало да се налази тражени податак). Затим се тај блок (лист) претражује док се податак не нађе (или се не испостави да податка нема).

 function тражи(унос r)
   u := корен
   while (u није лист) do
     изабери прави показивач у чвору
     иди у први чвор у који води показивач
     u := тренутни чвор
   претражи u за r

Овај псеудокод претпоставља да понављање није дозвољено.

Уметање

• изврши претрагу да утврдиш у који блок треба да се смести нови унос
• ако одговарајући блок није пун, додај унос.
• у супротном, подели блок.
• алоцирај нови лист и премести половину елемената из старог листа у нови.
• додај кључ и адресу најмањег кључа новог блока у родитељски чвор.
• ако је родитељски чвор пун, и њега подели.
• премести средњи кључ у родитељски чвор.
• понављај док се не појави родитељ који не мора да се дели.
• ако је потребно да се корен подели, направи нови корен који има један кључ и два показивача.

Карактеристике

За Б+ стабло реда b са h нивоа индекса:

• Максималан број уноса који могу да се ускладиште је $n=b^{h}$
• Минималан број кључева је $2(b/2)^{h-1}$
• Простор неопходан за складиштење стабла је $O(n)$
• Уметање уноса захтева $O(\log _{b}n)$ операција у најгорем случају.
• Проналажење уноса захтева $O(\log _{b}n)$ операција у најгорем случају.
• Брисање (претходно пронађеног) уноса захтева $O(\log _{b}n)$ операција у најгорем случају.
• Проналажење свих уноса који одговарају опсегу са k елемената у опсегу захтева $O(\log _{b}n+k)$ операција у најгорем случају.

Види још

• Бинарно стабло претраге
• Б# стабло
• Б-стабло
• Стратегија подели па владај