Меню

Структура на данните от B Tree и B + Tree в C ++

b tree b tree data structure c

Опитайте Нашия Инструмент За Премахване На Проблемите

Този урок за C ++ обяснява структурите на данни B Tree & B + Tree. Те се използват за съхраняване на данни в дискове, когато всички данни не могат да се съхраняват в основната памет:

B-дървото е самобалансирано дърво, както и специализирано m-way дърво, което се използва за достъп до диска.

Когато количеството данни за съхранение е много голямо, не можем да съхраним всички данни в основната памет. Следователно съхраняваме данни на диска. Достъпът до данни от диска отнема повече време в сравнение с достъпа до основната памет.

Когато броят на ключовете на данните, съхранявани на дискове, е много голям, достъпът до тях обикновено е под формата на блокове. Времето за достъп до тези блокове е право пропорционално на височината на дървото.

=> Щракнете тук за абсолютната серия за обучение на C ++.

B Tree и B + Tree

Какво ще научите:

B-дърво в C ++

B-Tree е плоско дърво, т.е. височината на B дървото е сведена до минимум. Вместо това във всеки възел на B-дървото се поставят толкова ключове. Като поддържа височината на B-дървото до минимум, достъпът е по-бърз в сравнение с други балансирани дървета като AVL дървета.

Типично B-дърво е показано по-долу:

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

изпълнение на двоично дърво c ++

По принцип размерът на възела в B-дървото се запазва същият като размера на блока.

По-долу са изброени някои от свойствата на B-Tree.

  • Всички листа на B-дървото са на едно и също ниво.
  • B-дърво от порядък m може да има най-много m-1 ключове и m деца.
  • Всеки възел в B-дърво има най-много m деца.
  • Коренният възел трябва да има поне два възела.
  • Всеки възел с изключение на кореновия възел и листния възел съдържа m / 2 деца.

След това обсъждаме някои от основните операции на B-дървото.

Основни операции на B-Tree

По-долу са дадени някои от основните операции на B-Tree.

# 1) Търсене

Търсенето в B дърво е подобно на това в BST. В горното дърво, ако искаме да потърсим т. 3, ще продължим по следния начин:

  • Сравнете 3 с коренните елементи. Ето, 3<6 and 3 <15. So we proceed to the left subtree.
  • Сравнете 3 с 4 в лявото поддърво. Като 3<4, we proceed to the left subtree of node 4.
  • Следващият възел има два ключа, 2 и 3. 3> 2, докато 3 = 3. Така че намерихме ключа в този възел. Върнете се на намереното място.

Търсенето в B дърво зависи от височината на дървото. Обикновено отнема O (log n) време за търсене на даден елемент.

# 2) Вмъкване

Вмъкването на нов елемент в дървото B се извършва на ниво листни възли.

Следва последователността от стъпки (алгоритъм) за вмъкване на нов елемент в B дървото.

  • Прекосете дървото B, за да намерите място във възлите на листа, за да вмъкнете елемента.
  • Ако листният възел съдържа ключове
  • В противен случай ако ключовете на възела на листа = m-1, тогава:
    • Поставете нов елемент във все по-голям брой елементи.
    • Вземете медианата на възлите и разделете възела на два възела.
    • Натиснете медиана към нейния родителски възел.
    • Ако ключът на родителския възел = m-1, повторете горните стъпки и за родителския възел. Това се прави, докато намерим подходящия листен възел.
  • Накрая вмъкнете елемента.

Демонстрирахме вмъкване в B дърво, както следва.

Нека вмъкнем елемент 70 в дървото, показано по-долу.

за какво се използва c ++

Даденото дърво е с минимална степен ‘m’ = 3. Следователно, всеки възел може да побере, 2 * m -1 = 5 ключа вътре в него.

Вмъкване на B-Tree

Сега вмъкваме елемент 70. Тъй като можем да имаме 5 ключа в възел, сравняваме елемент 70 с коренния елемент 30. Тъй като 70> 30, ще вмъкнем елемент 70 в дясното поддърво.

В дясното поддърво имаме възел с ключове 40, 50, 60. Тъй като всеки възел може да има 5 ключа в него, ще вмъкнем елемента 70 в самия този възел.

След вмъкването B-Tree изглежда по следния начин.

B дърво след вмъкване

# 3) Изтриване

Подобно на вмъкването, изтриването на ключа също се извършва на ниво листни възли. Но за разлика от вмъкването, изтриването е по-сложно. Ключът, който трябва да се изтрие, може да бъде или листен възел, или вътрешен възел.

За да изтрием ключ, следваме долната последователност от стъпки (алгоритъм).

1. Намерете листния възел.

две. В случай, че броят на ключовете в възел> m / 2, след това изтрийте дадения ключ от възела.

3. В случай, че листният възел няма m / 2 ключове, тогава трябва да попълним ключовете, като вземем ключове от дясното или лявото поддървета, за да поддържаме дървото B.

Следваме тези стъпки:

  • Ако лявото поддърво съдържа m / 2 елемента, тогава ние натискаме най-големия му елемент към родителския възел и след това преместваме междинния елемент на мястото, където ключът е бил изтрит.
  • Ако дясното поддърво съдържа m / 2 елемента, тогава ние натискаме най-малкия му елемент към родителския възел и след това преместваме междинния елемент на мястото, където ключът е бил изтрит.

Четири. Ако нито един възел няма m / 2 възела, тогава горните стъпки не могат да бъдат изпълнени, като по този начин ние създаваме нов листен възел, като обединяваме два листни възела и междинния елемент на родителския възел.

5. Ако родителят е без m / 2 възли, тогава ние повтаряме горните стъпки за въпросния родителски възел. Тези стъпки се повтарят, докато не получим балансирано B дърво.

Дадено по-долу е илюстрация за изтриване на възел от B дърво.

Помислете за следващото B дърво за пореден път.

Btree - Изтриване

Да приемем, че искаме да изтрием ключа 60 от дървото B. Ако проверим дървото B, можем да открием, че ключът, който трябва да бъде изтрит, присъства в листния възел. Изтриваме ключа 60 от този листен възел.

Сега дървото ще изглежда както е показано по-долу:

B-дърво след изтриване

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

Ако обаче трябваше да изтрием ключ 20, тогава само ключ 10 щеше да остане в левия възел на листа. В този случай ще трябва да преместим корен 30 към листния възел и да преместим ключ 40 към корена.

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

Преминаване в B дърво

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

Приложения на B дървета

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

B + дърво в C ++

B + дървото е продължение на B дървото. Разликата в B + дървото и B дървото е, че в B дървото ключовете и записите могат да се съхраняват като вътрешни, така и като листни възли, докато при B + дърветата записите се съхраняват като листни възли, а ключовете се съхраняват само във вътрешни възли.

Записите са свързани помежду си по начин на свързан списък. Тази подредба прави търсенето на B + дървета по-бързо и ефективно. Вътрешните възли на дървото B + се наричат ​​индексни възли.

кое е най-доброто шпионско приложение

Дърветата B + имат два реда, т.е. един за вътрешни възли и друг за листни или външни възли.

Пример за B + Tree е показан по-долу.

B + дърво

Тъй като B + дървото е продължение на B-дърво, основните операции, които обсъдихме в темата B-дърво, все още се запазват.

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

Предимства на дърветата B +

  • Можем да извлечем записи в равен брой достъпи до диска.
  • В сравнение с дървото B, височината на дървото B + е по-малка и остава балансирана.
  • Използваме ключове за индексиране.
  • Данните в дървото B + могат да бъдат достъпни последователно или директно, тъй като листните възли са подредени в свързан списък.
  • Търсенето е по-бързо, тъй като данните се съхраняват само в листови възли и като свързан списък.

Разлика между B-Tree и B + Tree

B-TreeB + дърво
Данните се съхраняват в листни възли, както и във вътрешни възли.Данните се съхраняват само в листови възли.
Търсенето е малко по-бавно, тъй като данните се съхраняват във вътрешни, както и в листни възли.Търсенето е по-бързо, тъй като данните се съхраняват само в листовите възли.
Няма излишни ключове за търсене.Възможно е да има излишни клавиши за търсене.
Операцията по изтриване е сложна.Операцията по изтриване е лесна, тъй като данните могат да бъдат директно изтрити от листовите възли.
Листовите възли не могат да бъдат свързани помежду си.Листовите възли са свързани заедно, за да образуват свързан списък.

Заключение

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

Търсенето на B-дърво е малко по-бавно, тъй като данните се съхраняват във вътрешни възли, както и във възли в тях. B + дървото е разширение на B-дърво и данните тук се съхраняват само в листни възли. Поради този фактор търсенето в B + дърво е по-бързо и ефективно.

=> Посетете тук за пълния списък с уроци за C ++.

Препоръчително четене

^