B+ ДЪРВО: Търсене, вмъкване и изтриване Operaции

Какво е B+ дърво?

A B+ дърво се използва предимно за имплементиране на динамично индексиране на множество нива. В сравнение с B-дърво, B+ дървото съхранява указателите към данни само в крайните възли на дървото, което прави процеса на търсене по-точен и бърз.

Правила за B+ дърво

Ето основните правила за B+ дърво.

• Листата се използват за съхраняване на записи на данни.
• Записите се съхраняват във вътрешните възли на дървото.
• Ако стойността на целевия ключ е по-малка от вътрешния възел, тогава се следва показалецът точно отляво.
• Ако стойността на целевия ключ е по-голяма или равна на вътрешния възел, тогава се следва показалецът точно от дясната му страна.
• Коренът има минимум две деца.

Защо да използвате B+ Tree

Ето причините за използване на B+ дърво:

• Ключовете се използват предимно за подпомагане на търсенето, като насочват към правилния лист.
• B+ дърво използва „коефициент на запълване“, за да управлява увеличаването и намаляването на дървото.
• В B+ дървета многобройни ключове могат лесно да бъдат поставени на страницата на паметта, тъй като те нямат данните, свързани с вътрешните възли. Следователно, той бързо ще получи достъп до данните в дървото, които са на листовия възел.
• Пълното сканиране на всички елементи изисква само едно линейно преминаване, тъй като всички листни възли на B+ дърво са свързани помежду си.

B+ Tree срещу B Tree

Ето основните разлики между B+ дърво и B дърво.

Търсене OperaАЦИ

В B+ дърво, търсенето е една от най-лесните процедури за изпълнение и дава бързи и точни резултати.

Приложим е следният алгоритъм за търсене:

• За да намерите необходимия запис, трябва да изпълните двоично търсене върху наличните записи в дървото.
• В случай на точно съвпадение с ключа за търсене, съответният запис се връща на потребителя.
• В случай, че точният ключ не бъде намерен чрез търсенето в родителския, текущия или листовия възел, тогава на потребителя се показва „ненамерено съобщение“.
• Процесът на търсене може да бъде повторен за по-добри и по-точни резултати.

Търсене Operaционен алгоритъм

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

Изход: Съвпадащият набор от записи срещу точния ключ се показва на потребителя; в противен случай на потребителя се показва неуспешен опит.

Поставете OperaАЦИ

За операцията по вмъкване е приложим следният алгоритъм:

• 50 процента от елементите във възлите се преместват на нов лист за съхранение.
• Родителят на новия лист е точно свързан с минималната ключова стойност и ново местоположение в Дървото.
• Разделете родителския възел на повече места, в случай че се използва напълно.
• Сега, за по-добри резултати, централният ключ е свързан с възела от най-високо ниво на този лист.
• Докато възелът от най-високо ниво не бъде намерен, продължавайте да повтаряте процеса, обяснен в горните стъпки.

Поставете Operaционен алгоритъм

1. If inserting at least 1 entry into the leaf container does not make it full, then add the record.
2. 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 tree.
   b. 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.

Изход: Алгоритъмът ще определи елемента и ще го вмъкне успешно в необходимия листов възел.

Горният примерен пример за B+ дърво е обяснен в стъпките по-долу:

• Първо, имаме 3 възела и първите 3 елемента, които са 1, 4 и 6, са добавени на съответните места във възлите.
• Следващата стойност в поредицата от данни е 12, която трябва да бъде част от Дървото.
• За да постигнете това, разделете възела и добавете 6 като указателен елемент.
• Сега се създава дясна йерархия на дърво и останалите стойности на данните се коригират съответно от keeping имайте предвид приложимите правила за равни или по-големи от стойности спрямо възлите ключ-стойност отдясно.

Изтрий OperaАЦИ

Сложността на процедурата за изтриване в B+ Tree надминава тази на функционалността за вмъкване и търсене.

Следният алгоритъм е приложим при изтриване на елемент от дървото B+:

• Първо, трябва да намерим запис в листа в дървото, който съдържа ключа и указателя, след което да изтрием записа от дървото, ако листът отговаря на точните условия за изтриване на запис.
• В случай че крайният възел отговаря само на задоволителния фактор да бъде наполовина запълнен, операцията е завършена; в противен случай крайният възел има минимален брой записи и не може да бъде изтрит.
• Другите свързани възли отдясно и отляво могат да освободят всички записи и след това да ги преместят в листа. Ако тези критерии не са изпълнени, тогава те трябва да комбинират листовия възел и свързания с него възел в дървовидната йерархия.
• При сливане на листов възел със съседите му отдясно или отляво, записите със стойности в листовия възел или свързания съсед, сочещи към възела от най-високо ниво, се изтриват.

Горният пример илюстрира процедурата за премахване на елемент от B+ дърво с определен ред.

• Първо, точните местоположения на елемента, който трябва да бъде изтрит, се идентифицират в дървото.
• Тук елементът, който ще бъде изтрит, може да бъде точно идентифициран само на ниво лист, а не на ниво индекс. Следователно, елементът може да бъде изтрит, без да се засягат правилата за изтриване, които са стойността на минималния ключ.

• В горния пример трябва да изтрием 31 от дървото.
• Трябва да намерим екземплярите на 31 в индекса и листа.
• Виждаме, че 31 е наличен както на ниво индексен, така и на ниво листен възел. Следователно, го изтриваме и от двата екземпляра.
• Но трябва да попълним индекса, сочещ към 42. Сега ще разгледаме правилното дете под 25 години и ще вземем минималната стойност и ще я поставим като индекс. Така че, тъй като 42 е единствената налична стойност, тя ще стане индексът.

Изтрий Operaционен алгоритъм

1) Start at the root and go up to the leaf node containing the key K.
2) Find the node n on the path from the root to the leaf node containing K.
   A. If n is root, remove K
      a. if root has more than one key, done
      b. if root has only K
         i)  if any of its child nodes can lend a node
             Borrow key from the child and adjust child links
         ii) Otherwise merge the children nodes. It will be a new root
      c. If n is an internal node, remove K
         i)  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 node
                Adjust child links
             Else
                Merge n with its sibling
                Adjust child links
      d. If n is a leaf node, remove K
         i)  If n has at least ceil(M/2) elements, done!
             In case the smallest key is deleted, push up the next key
         ii) If n has less than ceil(m/2) elements
             If the sibling can lend a key
                Borrow key from a sibling and adjust keys in n and its parent node
             Else
                Merge n and its sibling
                Adjust keys in the parent node

Изход: Ключът „K“ се изтрива и ключовете се заимстват от братя и сестри за коригиране на стойности в n и неговите родителски възли, ако е необходимо.

Въпроси и Отговори