B Дърво в структурата на данните: Търсене, Вмъкване, Изтриване

⚡ Умно обобщение

B-дървото в структурата на данните е самобалансиращо се дърво, което поддържа данните сортирани за бързо търсене, вмъкване и изтриване на диска. То обяснява правилата на B-дървото, неговата история и алгоритмите за търсене, вмъкване и изтриване с примери.

???? Самобалансиране: B-дървото поддържа всички листа на едно и също ниво и остава балансирано по време на всяка операция.
🔢 Поръчка (м): Степента m задава максималния брой деца (m) и ключове (m − 1) на възел.
🔍 Търсене: Търсенето започва от корена и се движи наляво или надясно чрез сравняване на ключа.
➕ Поставете: Вмъкването намира правилното място и разделя цял възел от средния му ключ.
➖ Изтрий: Изтриването обработва листни, вътрешни и коренни случаи, използвайки заемане и сливане.

Прочетете повече

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

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

B-дървото е специален вид дърво в структура от данни. През 1972 г. този метод е представен за първи път от Маккрайт и Байер, които го наричат „Височинно балансирано m-посочно дърво за търсене“. То ви помага да запазите сортираните данни и позволява различни операции като вмъкване, търсене и изтриване за по-кратко време.

Правила за B-Tree

Ето важни правила за създаване на B-дърво:

Всички листа ще бъдат създадени на едно и също ниво.
B-дървото се определя от число на степените, което също се нарича „ред“ (определено от външен участник, като програмист), наричано m нататък. Стойността на m зависи от размера на блока на диска, на който основно се намират данните.
Лявото поддърво на възела ще има по-малки стойности от дясната страна на поддървото. Това означава, че възлите също са сортирани във възходящ ред отляво надясно.
Максималният брой ключове, които коренният възел, както и неговите дъщерни възли, могат да съдържат, се изчислява по тази формула: m − 1, Например:
```
m = 4
max keys: 4 − 1 = 3
```

Всеки възел, с изключение на корена, трябва да съдържа минимален брой ключове от [m/2] − 1, Например:
```
m = 4
min keys: 4/2 − 1 = 1
```
Максималният брой дъщерни възли, които един възел може да има, е равен на неговата степен, което е m.
Минималните деца, които един възел може да има, са половината от поръчката, която е m/2 (взета е горната стойност).
Всички ключове в даден възел са сортирани във възходящ ред.

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

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

Намалява броя на четенията, направени на диска.
B-дърветата могат лесно да бъдат оптимизирани, за да се регулира размерът им (тоест броят на дъщерните възли) според размера на диска.
Това е специално проектирана техника за обработка на обемисти данни.
Това е полезен алгоритъм за бази данни и файлови системи.
Добър избор, когато става въпрос за четене и запис на големи блокове данни.

История на B Tree

Данните се съхраняват на диска на блокове. Тези данни, когато се въведат в основната памет (или RAM), се наричат структура от данни.
В случай на огромни данни, търсенето на един запис на диска изисква четене на целия диск; това увеличава времето и консумацията на основна памет поради високата честота на достъп до диска и размера на данните.
За да се преодолее това, се създават индексни таблици, които запазват референтните номера на записите въз основа на блоковете, в които се намират. Това драстично намалява консумацията на време и памет.
Тъй като имаме огромни данни, можем да създадем индексни таблици на много нива.
Многостепенен индекс може да бъде проектиран с помощта на B-дърво за съхранение.ping данните са сортирани по самобалансиращ се начин.

Търсене OperaАЦИ

Операцията за търсене е най-простата операция върху B дърво. Прилага се следният алгоритъм:

Нека ключът (стойността), която ще се търси, е „k“.
Започнете търсенето от корена и рекурсивно преминете надолу.
Ако k е по-малко от коренната стойност, търси се в лявото поддърво; ако k е по-голямо от коренната стойност, търси се в дясното поддърво.
Ако възелът има намереното k, просто върнете възела.
Ако k не се намери във възела, преминете надолу към дъщерния ключ с по-голям ключ.
Ако k не е намерено в дървото, връщаме NULL.

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

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

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

💡 СЪВЕТ: Това е следното не Вярно е за алгоритъма за вмъкване: „Тъй като възелът е пълен, той ще се раздели и след това ще бъде вмъкната нова стойност.“ Ключът се вмъква първо и едва след това възелът се разделя, ако надвиши максималния брой ключове.

В горния пример:

Потърсете подходящата позиция във възела за ключа.
Поставете ключа в целевия възел и проверете за правила.
След вмъкване, възелът има ли повече или равен на минималния брой ключове, който е 1? В този случай, да, има. Проверете следващото правило.
След вмъкването, има ли възелът повече от максималния брой ключове, който е 3? В този случай не, няма. Това означава, че B-дървото не нарушава никакви правила и вмъкването е завършено.

В горния пример:

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

В горния пример:

Възелът има по-малко от максималния брой ключове.
1 е вмъкнато до 3, но правилото за възходящ ред е нарушено.
За да се поправи това, ключовете се сортират.

По подобен начин, 13 и 2 могат лесно да бъдат вмъкнати във възела, тъй като те отговарят на правилото „по-малко от максималния брой ключове“ за възлите.

В горния пример:

Възелът има ключове, равни на макс.
Ключът е вмъкнат в целевия възел, но нарушава правилото за максимален брой ключове.
Целевият възел е разделен и средният ключ чрез ляво отклонение вече е родител на новите дъщерни възли.
Новите възли са подредени във възходящ ред.

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

Изтрий OperaАЦИ

Операцията за изтриване има повече правила от операциите за вмъкване и търсене. Прилага се следният алгоритъм:

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

Ако целевият ключ е в листовия възел

Target е в крайния възел, повече от min ключове. Изтриването му няма да наруши свойството на B-дървото.
Target е в крайния възел и има min ключови възли. Изтриването му ще наруши свойството на B-дървото.
Целевият възел може да заеме ключ от непосредствения ляв възел или непосредствения десен възел (брат/сестра).
Братът или сестрата ще кажат да ако има повече от минималния брой ключове.
Ключът ще бъде заимстван от родителския възел, максималната стойност ще бъде прехвърлена към родителския възел, максималната стойност на родителския възел ще бъде прехвърлена към целевия възел и целевата стойност ще бъде премахната.
Target е в крайния възел, но никой от братята и сестрите няма повече от минималния брой ключове: търсене на ключа, сливане със братята и сестрите и минималния брой родителски възли, общият брой ключове вече ще бъде повече от min, а целевият ключ ще бъде заменен с минималния брой ключове на родителски възел.

Ако целевият ключ е във вътрешен възел

Изберете или предшественик по ред, или наследник по ред.
В случай на предшественик по ред, ще бъде избран максималният ключ от лявото му поддърво.
В случай на наследник по ред, ще бъде избран минималният ключ от дясното му поддърво.
Ако предшественикът на целевия ключ по ред има повече от min ключовете, само тогава той може да замени целевия ключ с max на предшественика по ред.
Ако предшественикът на целевия ключ по ред няма повече от min ключове, потърсете минималния ключ на наследника по ред.
Ако и предшественикът, и наследникът на целевия ключ имат по-малко от min ключове, тогава обединете предшественика и наследника.

Ако целевият ключ е в коренен възел

Заменете с максималния елемент от поддървото-предшественик по ред.
Ако след изтриването, целта има по-малко от min ключове, тогава целевият възел ще заимства максималната стойност от своя брат/сестра чрез родителя на брат/сестра.
Максималната стойност на родителя ще бъде взета от целта, но с възлите на максималната стойност на брата/сестрата.

Сега нека разберем операцията за изтриване с пример.

Горната диаграма показва различни случаи на операцията по изтриване в B-дърво. Това B-дърво е от ред 5, което означава, че минималният брой дъщерни възли, които всеки възел може да има, е 3, а максималният брой дъщерни възли, които всеки възел може да има, е 5. Докато минималният и максималният брой ключове, които всеки възел може да има, са съответно 2 и 4.

В горния пример:

Целевият възел има целевия ключ за изтриване.
Целевият възел има ключове повече от минималния брой ключове.
Просто изтрийте ключа.

В горния пример:

Целевият възел има ключове, равни на минималния брой ключове, така че не можем да го изтрием директно, тъй като това ще наруши условията.

Сега следната диаграма обяснява как да изтриете този ключ:

Целевият възел ще заеме ключ от непосредствен брат/сестра, в този случай, предшественика по ред (ляв брат/сестра), защото няма наследник по ред (десен брат/сестра).
Максималната стойност на предшественика в реда ще бъде прехвърлена на родителя, а родителят ще прехвърли максималната стойност на целевия възел (вижте диаграмата по-долу).

Следващият пример илюстрира как да изтриете ключ, който се нуждае от стойност от неговия наследник по ред.

Целевият възел ще заеме ключ от непосредствен брат/сестра, в този случай, наследникът по ред (десен брат/сестра), защото неговият предшественик по ред (леви брат/сестра) има ключове, равни на минималния брой ключове.
Минималната стойност на наследника по ред ще бъде прехвърлена към родителя, а родителят ще прехвърли максималната стойност към целевия възел.

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

Обединете целевия възел с всеки от непосредствените му братя и сестри, заедно с родителския ключ.
Избира се ключът от родителския възел, който се намира между двата сливащи се възела.
Изтрийте целевия ключ от обединения възел.

Изтрий OperaПсевдо Code

private int removeBiggestElement()
{
    if (root has no child)
        remove and return the last element
    else {
        answer = subset[childCount-1].removeBiggestElement()
        if (subset[childCount-1].dataCount < MINIMUM)
            fixShort (childCount-1)
        return answer
    }
}

Изход: Най-големият елемент се изтрива от B-дървото.

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

Да. Инструментите с изкуствен интелект могат да генерират поетапни диаграми или анимации на вмъквания, разделяния и изтривания за даден ред. Това помага на учащите да видят как дървото се балансира отново, въпреки че трябва да проверите всяка стъпка спрямо правилата на B-дървото.

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

Възелът на двоичното дърво за търсене има най-много две деца и един ключ. Възелът на B-дървото може да съдържа много ключове и много деца, keeping дървото е кратко и намаляващо четенето от диск, което го прави идеално за бази данни и файлови системи.

Търсене, вмъкване и изтриване се извършват за време O(log n), където n е броят на ключовете. Тъй като всеки възел съдържа много ключове, дървото остава плитко, така че броят на достъпите до диска е много малък.

B Дърво в структурата на данните: Търсене, Вмъкване, Изтриване