Википедија

K-Д-Б стабло

У информатици, К-Д-Б стабло (К - димензионално Б - стабло) је структура података за поделу к - димензионалног простора за претраживање. Циљ К-Д-Б стабла је да се обезбеди ефикасна претрага балансираног К-Д стабла, пружајући блоковски-оријентисано складиштење Б стабла ради оптимизације приступа спољној меморији.[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% искоришћеност простора статичког К-Д-Б стабла. Уместо одржавања и ребалансирања једног стабла, скуп од   К-Д-Б стабла се одржавају и поново праве у редовним интервалима.[3] У овом случају,   је величина међумеморије у броју тачака.

Референце уреди

  1. ^ Robinson, John (1981). „The K-D-B-Tree: A Search Structure for Large Multidimensional Dynamic Indexes”. Proceedings of the 1981 ACM SIGMOD international conference on Management of data: 10—18. doi:10.1145/582318.582321. Приступљено 8. 4. 2014. 
  2. ^ Lomet, David; Salzberg, Betty (децембар 1990). „The hB-tree: a multiattribute indexing method with good guaranteed performance”. ACM Transactions on Database Systems (TODS). 15 (4): 625—658. doi:10.1145/99935.99949. Приступљено 8. 4. 2014. 
  3. ^ Procopiuc, Octavian; Agarwal, Pankaj; Arge, Lars; Jeffrey Scott Vitter (2003). „Bkd-Tree: A Dynamic Scalable kd-Tree”. Advances in Spatial and Temporal Databases. Lecture Notes in Computer Science. 2750: 46—65. doi:10.1007/978-3-540-45072-6_4. 
Преузето из „https://sr.wikipedia.org/w/index.php?title=K-Д-Б_стабло&oldid=26755348”