B ДЪРВО в структурата на данните: Търсене, Вмъкване, Изтриване Operaция Пример

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

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

• Всички листа ще бъдат създадени на едно и също ниво.
• B-Tree се определя от числова степен, която също се нарича „ред“ (посочена от външен актьор, като програмист), наричана

  m

  нататък. Стойността на

  m

  зависи от размера на блока на диска, на който основно се намират данните.

• Лявото поддърво на възела ще има по-малки стойности от дясната страна на поддървото. Това означава, че възлите също са сортирани във възходящ ред отляво надясно.
• Максималният брой дъщерни възли, коренният възел, както и неговите дъщерни възли могат да съдържат, се изчисляват по тази формула:

  m – 1

  Например:

  m = 4
  max keys: 4 – 1 = 3
  

• Всеки възел, с изключение на root, трябва да съдържа минимум ключове от

  [m/2]-1

  Например:

  m = 4
  min keys: 4/2-1 = 1
  

• Максималният брой дъщерни възли, които един възел може да има, е равен на неговата степен, което е

  m

• Минималните деца, които един възел може да има, са половината от поръчката, която е m/2 (взета е горната стойност).
• Всички ключове в даден възел са сортирани във възходящ ред.

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

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

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

История на B Tree

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

Търсене OperaАЦИ

Операцията за търсене е най-простата операция на B Tree.

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

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

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

Тъй като B Tree е самобалансиращо се дърво, не можете насила да вмъкнете ключ във всеки възел.

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

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

TIP	Следното не е вярно за алгоритъма за вмъкване: Тъй като възелът е пълен, следователно той ще се раздели и след това ще бъде вмъкната нова стойност

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

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

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

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

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

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

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

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

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

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

Изтрий OperaАЦИ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вижте процедурата за изтриване на такъв ключ:

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

Изтрий Operaция Псевдо код

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-дървото.

Oбобщение

• B Tree е самобалансираща се структура от данни за по-добро търсене, вмъкване и изтриване на данни от диска.
• B Дървото се регулира от определената степен
• B Ключовете и възлите на дървото са подредени във възходящ ред.
• Операцията за търсене на B Tree е най-простата, която винаги започва от корена и започва да проверява дали целевият ключ е по-голям или по-малък от стойността на възела.
• Операцията за вмъкване на B Tree е доста подробна, която първо намира подходяща позиция на вмъкване за целевия ключ, вмъква го, оценява валидността на B Tree спрямо различни случаи и след това съответно преструктурира възлите на B Tree.
• Операцията за изтриване на B Tree първо търси целевия ключ за изтриване, изтрива го, оценява валидността въз основа на няколко случая като минимални и максимални ключове на целевия възел, братя и сестри и родител.