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

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

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

B-Tree е специален вид дърво в структура от данни. През 1972 г. този метод е въведен за първи път от McCreight, а Bayer го нарича Height Balanced m-way Search Tree. Помага ви да запазите сортирани данни и разрешени различни операции като вмъкване, търсене и изтриване за по-малко време.

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

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

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

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

    m

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

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

    Например:

    m = 4
    max keys: 4 – 1 = 3
    

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

  • Всеки възел, с изключение на 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 Следното не е вярно за алгоритъма за вмъкване:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изтрий OperaАЦИ

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

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

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

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

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

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

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

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

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

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

Изтрий OperaАЦИ

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

Изтрий OperaАЦИ

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

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

Изтрий OperaАЦИ

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

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

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

Изтрий OperaАЦИ

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

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

Изтрий OperaАЦИ

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

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

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

Изтрий OperaАЦИ

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

Изтрий 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 първо търси целевия ключ за изтриване, изтрива го, оценява валидността въз основа на няколко случая като минимални и максимални ключове на целевия възел, братя и сестри и родител.