Б + ДРВО: Пример претраживања, уметања и брисања

Преглед садржаја:

Anonim

Шта је Б + дрво?

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

У овом водичу за Б + Трее научићете:

  • Шта је Б + дрво?
  • Правила за стабло Б +
  • Зашто користити Б + Трее
  • Б + Трее насупрот Б Трее
  • Операција претраживања
  • Инсерт Оператион
  • Делете Оператион

Правила за стабло Б +

Ево основних правила за дрво Б +.

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

Зашто користити Б + Трее

Ево разлога за употребу стабла Б +:

  • Кључеви се првенствено користе за помоћ у претрази усмеравањем на одговарајући лист.
  • Б + Трее користи „фактор попуњавања“ за управљање повећањем и смањењем стабла.
  • У стаблима Б +, бројни кључеви се лако могу поставити на страницу меморије, јер немају податке повезане са унутрашњим чворовима. Стога ће брзо приступити подацима о дрвету који се налазе на чвору листа.
  • Свеобухватно потпуно скенирање свих елемената је дрво којем је потребан само један линеарни пролаз јер су сви чворови листа Б + стабла повезани једни с другима.

Б + Трее насупрот Б Трее

Овде су главне разлике између Б + Трее и Б Трее

Б + дрво Б Трее
Тастери за претрагу се могу поновити. Кључеви за претрагу не могу бити сувишни.
Подаци се чувају само на чворовима листа. Подаци и чворови листа и унутрашњи чворови могу да чувају податке
Подаци ускладиштени на чвору листа чине претрагу тачнијом и бржом. Претраживање је споро због података ускладиштених на Леаф-у и унутрашњим чворовима.
Брисање није тешко јер се елемент уклања само са чвора листа. Брисање елемената је сложен и дуготрајан процес.
Повезани чворови листа чине претрагу ефикасном и брзом. Не можете повезати чворове листова.

Операција претраживања

У Б + Трее-у је претрага један од најлакших поступака за извршавање и из ње се добијају брзи и тачни резултати.

Применљив је следећи алгоритам претраживања:

  • Да бисте пронашли тражени запис, морате извршити бинарну претрагу доступних записа у Дрвету.
  • У случају тачног подударања са кључем за претрагу, одговарајући запис се враћа кориснику.
  • У случају да претрага у родитељском, тренутном или лисном чвору није пронађена тачно у кључу, тада се кориснику приказује „порука није пронађена“.
  • Поступак претраге се може поново покренути за боље и тачније резултате.

Алгоритам операције претраживања

1. Call the binary search method on the records in the B+ Tree.2. If the search parameters match the exact keyThe accurate result is returned and displayed to the userElse, if the node being searched is the current and the exact key is not found by the algorithmDisplay the statement "Recordset cannot be found."

Излаз :

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

Инсерт Оператион

Следећи алгоритам је применљив за операцију уметања:

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

Уметни алгоритам операције

1. Even inserting at-least 1 entry into the leaf container does not make it full then add the record2. Else, divide the node into more locations to fit more records.a. Assign a new leaf and transfer 50 percent of the node elements to a new placement in the treeb. The minimum key of the binary tree leaf and its new key address are associated with the top-level node.c. Divide the top-level node if it gets full of keys and addresses.i. Similarly, insert a key in the center of the top-level node in the hierarchy of the Tree.d. Continue to execute the above steps until a top-level node is found that does not need to be divided anymore.3) Build a new top-level root node of 1 Key and 2 indicators.

Излаз :

Алгоритам ће одредити елемент и успешно га убацити у потребан чвор чвора.

Горњи пример узорка Б + Трее објашњен је у следећим корацима:

  • Прво, имамо 3 чвора, а прва 3 елемента, који су 1, 4 и 6, додају се на одговарајуће локације у чворовима.
  • Следећа вредност у низу података је 12 која треба да буде део Стабла.
  • Да бисте то постигли, поделите чвор, додајте 6 као елемент показивача.
  • Сада се креира десна хијерархија стабла и преостале вредности података се прилагођавају у складу с тим имајући на уму примењива правила једнака или већа од вредности у односу на чворове кључ / вредност с десне стране.

Делете Оператион

Сложеност поступка брисања у стаблу Б + премашује сложеност функције уметања и претраживања.

Следећи алгоритам је применљив приликом брисања елемента из Б + стабла:

  • Прво, морамо да пронађемо унос листа у дрвету који држи кључ и показивач. , обришите унос листа са дрвета ако лист испуњава тачне услове брисања записа.
  • У случају да листни чвор задовољава само задовољавајући фактор да је напола пун, тада је операција завршена; у супротном, чвор Леаф има најмање уноса и не може се избрисати.
  • Остали повезани чворови с десне и леве стране могу ослободити све уносе, а затим их преместити на Лист. Ако ови критеријуми нису испуњени, они би требало да комбинују лисни чвор и његов повезани чвор у хијерархији стабла.
  • Спајањем лисног чвора са суседима с десне или леве стране, уноси вредности у чвору листа или повезаног суседа који упућују на чвор највишег нивоа се бришу.

Горњи пример илуструје поступак уклањања елемента са Б + стабла одређеног реда.

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

  • У горњем примеру морамо да избришемо 31 са стабла.
  • Морамо да пронађемо примерке 31 у индексу и листу.
  • Видимо да је 31 доступан и на нивоу индекса и на нивоу чвора Леаф. Стога га бришемо из оба случаја.
  • Али, морамо попунити индекс који показује на 42. Сада ћемо погледати право дете млађе од 25 година и узети минималну вредност и поставити га као индекс. Дакле, 42 као једина присутна вредност постаће индекс.

Избришите алгоритам операције

1) Start at the root and go up to leaf node containing the key K2) Find the node n on the path from the root to the leaf node containing KA. If n is root, remove Ka. if root has more than one key, doneb. if root has only Ki) if any of its child nodes can lend a nodeBorrow key from the child and adjust child linksii) Otherwise merge the children nodes. It will be a new rootc. If n is an internal node, remove Ki) If n has at least ceil(m/2) keys, done!ii) If n has less than ceil(m/2) keys,If a sibling can lend a key,Borrow key from the sibling and adjust keys in n and the parent nodeAdjust child linksElseMerge n with its siblingAdjust child linksd. If n is a leaf node, remove Ki) If n has at least ceil(M/2) elements, done!In case the smallest key is deleted, push up the next keyii) If n has less than ceil(m/2) elementsIf the sibling can lend a keyBorrow key from a sibling and adjust keys in n and its parent nodeElseMerge n and its siblingAdjust keys in the parent node

Излаз :

Кључ „К“ је избрисан, а кључеви су позајмљени од браће и сестара ради прилагођавања вредности у н и његових матичних чворова ако је потребно.

Резиме:

  • Б + Трее је самобалансирајућа структура података за извршавање тачног и бржег претраживања, уметања и брисања поступака на подацима
  • Комплетне податке или делимичне податке можемо лако добити, јер пролазак кроз повезану структуру стабла то чини ефикасним.
  • Структура стабла Б + расте и смањује се са повећањем / смањењем броја сачуваних записа.
  • Чување података на чворовима листа и накнадно гранање унутрашњих чворова очигледно скраћује висину стабла, што смањује операције уноса и излаза диска, на крају трошећи много мање простора на уређајима за складиштење.