Овај чланак је започет или проширен кроз пројекат семинарских радова. Потребно је проверити превод, правопис и вики-синтаксу. Када завршите са провером, допишете да након |проверено=.

У информатици, К-Д-Б стабло (К - димензионално Б - стабло) је структура података за поделу к - димензионалног простора за претраживање. Циљ К-Д-Б стабла је да се обезбеди ефикасна претрага балансираног К-Д стабла, пружајући блоковски-оријентисано складиштење Б стабла ради оптимизације приступа спољној меморији.^[1]

Слично као к-д стабло, К-Д-Б стабло организује тачке у к-димензионалном простору и користи се за претраживање опсега и мулти-димензионалне упите над базама података. К-Д-Б стабло дели простор на два подпростора упоређивањем елемената у једном домену. Користећи 2-Д-Б стабло (2-димензионално К-Д-Б стабло) као пример, простор је подељен на исти начин као и код к-д стабла - користећи тачку у само једном од домена, или оса у овом случају, све остале вредности су мање или веће од тренутне вредности, и падају лево и десно од равни која дели простор.

За разлику од к-д стабла, није свака половина простора сама себи чвор. Уместо тога, као у Б-стаблу, чворови у К-Д-Б стаблу се чувају као странице, а стабло чува показивач ка страници у корену.

К-Д-Б стабло садржи две врсте страница:

• Странице-региони: Колекција парова (регион,дете) који садржи опис граничног региона, заједно са показивачем ка страници-детету која одговара том региону.
• Странице-тачке: Колекција парова (тачка, локације). У случају базе података, локација може да показује на индекс записа у бази, док се за тачке у к-димензионалном простору може посматрати као координата тачке у том простору.

Преливање странице се јавља приликом убацивања елемената у К-Д-Б стабло, ако чвор пређе своју оптималну величину. Пошто је сврха К-Д-Б стабла да оптимизује приступ спољној меморији, страница се сматра преливеном или препуњеном када величина чвора пређе величину странице спољне меморије.

Током додавања/брисања, К-Д-Б стабло задржава одређени скуп особина:

• Граф је вишепутно стабло. Странице-региони увек показују на страницу децу и не могу бити празне. Странице-тачке су листови чворова стабла.
• Као и Б-стабло, дужина путање до листа стабла је иста за све упите.
• Региони који чине регион страница су раздвојени.
• Ако је корен регион страница, скуп њених региона је цео простор за претрагу.
• Када је дете пара (регион, дете) у регион страници такође регион страница, унија свих региона у детету је регион.
• Са друге стране, у претходном случају, ако је дете пара тачка страница, све тачке у детету морају бити садржане у региону.

Упити на К-Д-Б стабло су претрага опсега над интервалима у свим доменима или осама стабла. Ова колекција интервала се зове регион упита. У k-простору, регион упита се може сагледати као гранични волумен око неког подпростора у целом k-димензионалном простору за претрагу. Упит може да спада у једну од три категорије:

• Распон неких интервала је цео домен или оса, што упит чини упитом делимичног опсега.
• Неки интервали су тачке, други су пуни домени, па је упит са делимичним поклапањем.
• Сви интервали су тачке, тако је и гранични волумен тачка. То упит чини упитом са потпуним поклапањем.

1. Ако је корен стабла NULL, прекинути, у супротном нека страна буде корен.
2. Ако је страна тачка страница, врати тачку у (тачка, локација) пару који се налази у региону упита.
3. Иначе, страна је регион страница, тако да за све парове (регион, дете) где се регион и регион упита секу, постави страницу да буде дете и настави од корака 2.

Због тога што додавање у К-Д-Б стабло може захтевати дељење странице у случају преливања/преплављења странице, морамо прво дефинисати операцију поделе.

Регион страница је подељена дуж неке равни, и од ње настају две нове регион странице, лева и десна страница. Ове странице су попуњене регионима из старе странице, која се брише. Затим, за сваки (регион, дете) пар у оригиналној регион страни, дете које памтимо је страна и регион је гранични регион:

1. Ако регион у потпуности лежи са леве стране равни поделе, додати (регион, дете) левој страни.
2. Ако регион у потпуности лежи са десне стране равни поделе, додати (регион, дете) десној страни.
3. Иначе:
   1. Рекурзивно делимо дете по равни поделе, чиме добијамо нову леву страницу и нову десну страницу.
   2. Дељењем региона по равни поделе добијамо леви регион и десни регион.
   3. Додајемо (леви регион, нову леву страну) левој страни и (десни регион, нову десну страну) десној страни.

Користећи алгоритам поделе, уметање новог (тачка, локација) пара се може извести на следећи начин:

1. Ако је корена страница NULL, направи нову тачка-страницу која садржи (тачку, локацију) и постави корену страницу на ту вредност.
2. У случају потпуног поклапања упита, нађи страницу у коју треба додати тачку. Ако тачка већ постоји у страници, заврши.
3. Додај (тачка, локација) у страницу. Ако је страница препуњена, означи страницу са страница.
4. Нека је стара страница једнака страници. Изабери неки елемент и домен/осу за дефинисање равни раздвајања, тако да се страница раздвоји на 2 странице од којих ниједна неће бити препуњена после додавања нове тачке. Раздвој страницу на 2 странице, нову леву страницу и нову десну страницу, и 2 нова региона, нови леви регион и нови десни регион.
5. Ако је страница била у корену, иди на корак 6. У супротном, страница постаје родитељ странице. Замени (регион, стара страница) у страници са (нови леви регион, нова лева страница) и (нови десни регион, нова десна страница). Ако је страница препуњена понови корак 4, у супротном заврши.
6. Нека леви регион буде читав простор претраживања лево од равни раздвајања и нека десни регион буде простор претраживања десно, као резултати корака 4. Постави корену страницу тако да садржи леви регион и десни регион.

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

Брисање из К-Д-Б стабла је врло једноставно ако нема минималних захтева за коришћење меморије. Користимо тачно поклапање упита да пронађемо (тачку, локацију) пар и једноставно уклонимо тај пар из стабла уколико он постоји.

Због тога што брисање из К-Д-Б стабла може довести до тога да страница има јако мало података, може бити потребно да се стабло реорганизује како би испунило минималне критеријуме у коришћењу меморије. Алгоритам реорганизације који се користи уколико страница има мало података је следећи:

1. Нека страна буде родитељ од П и садржи (регион, П).
2. Пронађи суседне регионе на страни тако да њихова унија представља правоугаони регион. Ови региони се сматрају спојивим. Нека Р означава скуп ових региона.
3. Утопи скуп Р у једну страницу С, и ако је С препуна понови све док ниједна од добијених страница није препуна.
4. Замени скуп региона Р на страни са страницама добијеним дељењем С.

Као и у к-д стаблу, измене у К-Д-Б стаблу могу довести до потребе рекурзивног раздвајања чворова. Ово је врло неефикасно и може довести до неоптималног коришћења меморије јер се ствара много празних листова. Lomet и Salcberg су предложили структуру под називом hB стабло како би побољшали перфомансе К-Д-Б стабла ограничавајући поделе које настају након уметања. Ово је постигнуто не само чувањем региона као правоугаоника већ као правоугаоника којима је уклоњен правоугаоник из центра.^[2]

У скорије време, Б-К-Д стабло је предложено као средство да се обезбеде брзи упити и 100% искоришћеност простора статичког К-Д-Б стабла. Уместо одржавања и ребалансирања једног стабла, скуп од ${\displaystyle \log _{2}(N/M)}$ К-Д-Б стабла се одржавају и поново праве у редовним интервалима.^[3] У овом случају, ${\displaystyle M}$ је величина међумеморије у броју тачака.