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