Преди разбирането Б дърво и B+ дърво разлики, трябва да знаем B дървото и B+ дървото поотделно.

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

Б дърво е самобалансиращо се дърво и е m-way дърво, където m определя реда на дървото. Btree е обобщение на Двоично дърво за търсене в който възел може да има повече от един ключ и повече от две деца в зависимост от стойността на м . В дървото B данните са посочени в сортиран ред с по-ниски стойности в лявото поддърво и по-високи стойности в дясното поддърво.

урок по микроуслуги

Свойства на B дърво

Следните са свойствата на B дървото:

• В B дървото всички листови възли трябва да са на едно и също ниво, докато в случай на двоично дърво листовите възли могат да бъдат на различни нива.

Нека разберем това свойство чрез пример.

В горното дърво всички листови възли не са на едно и също ниво, но имат най-много две деца. Следователно можем да кажем, че горното дърво е a двоично дърво но не и B дърво.

• Ако Btree има ред от m, тогава всеки възел може да има максимум м В случай на минимални деца, листовите възли имат нула деца, коренният възел има две деца, а вътрешните възли имат таван от m/2.
• Всеки възел може да има максимум (m-1) ключове. Например, ако стойността на m е 5, тогава максималната стойност на ключовете е 4.
• Основният възел има минимум един ключ, докато всички останали възли с изключение на основния възел имат (таван от m/2 минус - 1) минимум ключове.
• Ако извършим вмъкване в B дървото, тогава възелът винаги се вмъква в листовия възел.

Да предположим, че искаме да създадем B дърво от ред 3, като вмъкнем стойности от 1 до 10.

Етап 1: Първо създаваме възел с 1 стойност, както е показано по-долу:

Стъпка 2: Следващият елемент е 2, който идва след 1, както е показано по-долу:

Стъпка 3: Следващият елемент е 3 и се вмъква след 2, както е показано по-долу:

Тъй като знаем, че всеки възел може да има 2 максимални ключа, така че ще разделим този възел през средния елемент. Средният елемент е 2, така че се премества към своя родител. Възел 2 няма родител, така че ще стане основен възел, както е показано по-долу:

Стъпка 4: Следващият елемент е 4. Тъй като 4 е по-голямо от 2 и 3, той ще бъде добавен след 3, както е показано по-долу:

Стъпка 5: Следващият елемент е 5. Тъй като 5 е по-голямо от 2, 3 и 4, то ще бъде добавено след 4, както е показано по-долу:

Тъй като знаем, че всеки възел може да има 2 максимални ключа, така че ще разделим този възел през средния елемент. Средният елемент е 4, така че се премества към своя родител. Родителят е възел 2; следователно 4 ще се добави след 2, както е показано по-долу:

Стъпка 6: Следващият елемент е 6. Тъй като 6 е по-голямо от 2, 4 и 5, така че 6 ще дойде след 5, както е показано по-долу:

Стъпка 7: Следващият елемент е 7. Тъй като 7 е по-голямо от 2, 4, 5 и 6, така че 7 ще дойде след 6, както е показано по-долу:

Тъй като знаем, че всеки възел може да има 2 максимални ключа, така че ще разделим този възел през средния елемент. Средният елемент е 6, така че се премества към своя родител, както е показано по-долу:

Но 6 не може да се добави след 4, защото възелът може да има 2 максимални ключа, така че ще разделим този възел през средния елемент. Средният елемент е 4, така че се премества към своя родител. Тъй като възел 4 няма родител, възел 4 ще стане основен възел, както е показано по-долу:

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

The B+ дърво е известен също като усъвършенствано самобалансирано дърво, защото всеки път от корена на дървото до листа на дървото има еднаква дължина. Тук същата дължина означава, че всички листови възли се намират на едно и също ниво. Няма да се случи някои от листните възли да се появят на трето ниво, а някои от тях на второ ниво.

B+ дървовидният индекс се счита за многостепенен индекс, но B+ дървовидната структура не е подобна на последователните файлове на многостепенния индекс.

Защо се използва дървото B+?

B+ дърво се използва за съхраняване на записите много ефективно чрез съхраняване на записите по индексиран начин с помощта на B+ дървовидна индексирана структура. Благодарение на многостепенното индексиране, достъпът до данни става по-бърз и лесен.

B+ дървовидна възлова структура

Структурата на възлите на B+ дървото съдържа указатели и ключови стойности, показани на фигурата по-долу:

Както можем да забележим в горната структура на B+ дървовиден възел, че тя съдържа n-1 ключови стойности (k₁към к_n-1) и n указателя (стр₁Горна част_н).

Стойностите на ключовете за търсене, които са поставени във възела, се съхраняват в сортиран ред. По този начин, ако iазй.

Ограничение за различни видове възли

Нека 'b' е редът на дървото B+.

Non-Leaf възел

Нека 'm' представлява броя на децата на възел, тогава връзката между реда на дървото и броя на децата може да бъде представена като:

Нека k представлява стойностите на ключа за търсене. Връзката между реда на дървото и ключа за търсене може да бъде представена като:

Тъй като знаем, че броят на указателите е равен на стойностите на ключа за търсене плюс 1, така че математически може да се запише като:

Брой указатели (или деца) = Брой клавиши за търсене + 1

Следователно максималният брой указатели ще бъде 'b', а минималният брой указатели ще бъде таванната функция на b/2.

Листен възел

hashset java

Листовият възел е възел, който се появява на последното ниво на B+ дървото и всеки листов възел използва само един указател, за да се свърже един с друг, за да осигури последователен достъп на листовото ниво.

В листовия възел максималният брой деца е:

Максималният брой ключове за търсене е:

Коренен възел

Максималният брой деца в случай на коренния възел е: b

Минималният брой деца е: 2

Специални случаи в B+ дърво

Случай 1: Ако коренният възел е единственият възел в дървото. В този случай коренният възел става листовият възел.

В този случай максималният брой деца е 1, т.е. самият коренов възел, докато минималният брой деца е b-1, което е същото като това на листовия възел.

Представяне на листен възел в B+ дърво

В горната фигура, '.' представлява указателя, докато 10, 20 и 30 са ключовите стойности. Указателят съдържа адреса, на който се съхранява стойността на ключа, както е показано на фигурата по-горе.

Пример за B+ дърво

В горната фигура възелът съдържа три ключови стойности, т.е. 9, 16 и 25. Указателят, който се появява преди 9, съдържа ключовите стойности, по-малки от 9, представени от k_аз. Указателят, който се появява преди 16, съдържа ключовите стойности, по-големи или равни на 9, но по-малки от 16, представени от kj. Указателят, който се появява преди 25, съдържа ключовите стойности, по-големи или равни на 16, но по-малки от 25, представени от k_н.

Разлики между B дърво и B+ дърво

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