Какво е B + дърво?
A B + дърво се използва предимно за прилагане на динамичен индексиране на няколко нива. В сравнение с B-Tree, B + Tree съхранява указателите за данни само в листните възли на дървото, което прави търсенето по-точно и по-бързо.
В този урок B + Tree ще научите:
- Какво е B + дърво?
- Правила за B + Tree
- Защо да използвате B + Tree
- B + Tree срещу B Tree
- Операция за търсене
- Вмъкване на операция
- Изтриване на операцията
Правила за B + Tree
Ето основните правила за B + Tree.
- Листата се използват за съхраняване на записи на данни.
- Той се съхранява във вътрешните възли на дървото.
- Ако стойността на целевия ключ е по-малка от вътрешния възел, тогава се следва точката точно от лявата му страна.
- Ако стойността на целевия ключ е по-голяма или равна на вътрешния възел, тогава се следва точката точно от дясната му страна.
- Коренът има минимум две деца.
Защо да използвате B + Tree
Ето причините за използването на B + Tree:
- Ключовете се използват предимно за подпомагане на търсенето чрез насочване към правилния лист.
- B + Tree използва "коефициент на запълване", за да управлява увеличаването и намаляването на дървото.
- В B + дърветата многобройни ключове могат лесно да бъдат поставени на страницата на паметта, тъй като те нямат данните, свързани с вътрешните възли. Следователно той ще има бърз достъп до дървесни данни, които се намират на листния възел.
- Цялостното пълно сканиране на всички елементи е дърво, което се нуждае само от един линеен проход, тъй като всички листни възли на B + дърво са свързани помежду си.
B + Tree срещу B Tree
Ето основните разлики между B + Tree и B Tree
| B + дърво | B Дърво |
| Клавишите за търсене могат да се повтарят. | Клавишите за търсене не могат да бъдат излишни. |
| Данните се записват само на листовите възли. | Както листовите, така и вътрешните възли могат да съхраняват данни |
| Данните, съхранявани на листния възел, правят търсенето по-точно и по-бързо. | Търсенето е бавно поради данни, съхранявани в Leaf и вътрешни възли. |
| Изтриването не е трудно, тъй като елементът се премахва само от листния възел. | Изтриването на елементи е сложен и отнемащ време процес. |
| Свързаните листни възли правят търсенето ефективно и бързо. | Не можете да свързвате листни възли. |
Операция за търсене
В B + Tree търсенето е една от най-лесните процедури за изпълнение и получаване на бързи и точни резултати от него.
Следният алгоритъм за търсене е приложим:
- За да намерите необходимия запис, трябва да изпълните двоичното търсене на наличните записи в дървото.
- В случай на точно съвпадение с ключа за търсене, съответният запис се връща на потребителя.
- В случай че точният ключ не се намира при търсенето в родителския, текущия или листния възел, тогава на потребителя се показва „not found message“.
- Процесът на търсене може да бъде повторен за по-добри и по-точни резултати.
Алгоритъм на операцията за търсене
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.
Изход :
Алгоритъмът ще определи елемента и ще го вмъкне успешно в необходимия листен възел.
Горният пример за пример B + Tree е обяснен в стъпките по-долу:
- Първо, имаме 3 възла и първите 3 елемента, които са 1, 4 и 6, се добавят на подходящи места във възлите.
- Следващата стойност в поредицата от данни е 12, която трябва да стане част от дървото.
- За да постигнете това, разделете възела, добавете 6 като елемент на указател.
- Сега се създава дясна йерархия на дърво и останалите стойности на данните се коригират съответно, като се имат предвид приложимите правила, равни или по-големи от стойностите спрямо възлите ключ-стойност вдясно.
Изтриване на операцията
Сложността на процедурата за изтриване в B + Tree надминава тази на функцията за вмъкване и търсене.
Следният алгоритъм е приложим при изтриване на елемент от дървото B +:
- Първо, трябва да намерим листен лист в дървото, който държи ключа и показалеца. , изтрийте записа на листа от дървото, ако листът отговаря на точните условия за изтриване на записа.
- В случай, че листният възел отговаря само на задоволителния фактор, че е наполовина пълен, тогава операцията е завършена; в противен случай възелът Leaf има минимални записи и не може да бъде изтрит.
- Другите свързани възли отдясно и отляво могат да освободят всички записи, след което да ги преместят в листа. Ако тези критерии не са изпълнени, те трябва да комбинират листния възел и свързания с него възел в йерархията на дървото.
- При сливане на листовия възел със съседите му отдясно или отляво, записите на стойности в листовия възел или свързания съсед, сочещ към възела от най-високо ниво, се изтриват.
Примерът по-горе илюстрира процедурата за премахване на елемент от дървото B + от определен ред.
- Първо, точните местоположения на елемента, който ще бъде изтрит, са идентифицирани в дървото.
- Тук елементът, който трябва да бъде изтрит, може да бъде точно идентифициран само на нивото на листа, но не и при разположението на индекса. Следователно елементът може да бъде изтрит, без да се засяга правилата за изтриване, което е стойността на ключа минимум.
- В горния пример трябва да изтрием 31 от дървото.
- Трябва да намерим екземплярите от 31 в Index и Leaf.
- Можем да видим, че 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
Изход :
Ключът "K" се изтрива и ключовете са взаимствани от братя и сестри за коригиране на стойности в n и неговите родителски възли, ако е необходимо.
Резюме:
- B + Tree е самобалансираща се структура на данни за изпълнение на точно и по-бързо търсене, вмъкване и изтриване на процедури върху данни
- Ние можем лесно да извлечем пълни данни или частични данни, защото преминаването през свързаната дървесна структура го прави ефективен.
- Структурата на дървото B + расте и се свива с увеличаване / намаляване на броя на съхранените записи.
- Съхранението на данни на листовите възли и последващото разклоняване на вътрешните възли очевидно съкращава височината на дървото, което намалява операциите за въвеждане и извеждане на диска, като в крайна сметка консумира много по-малко място на устройствата за съхранение.