Разлика между B-tree и Binary tree
Съдържание
- Сравнителна диаграма
- Определение на B-дърво
- Свойства на B-дърво от ред M
- Определение на Binary tree
- Техники на преминаване
- заключение
B-tree и Binary tree са типовете нелинейни структури от данни. Въпреки че термините изглеждат сходни, но са различни във всички аспекти. Двоично дърво се използва, когато записите или данните се съхраняват в оперативната памет вместо диск, тъй като скоростта на достъп на RAM е много по-висока от диска. От друга страна, B-tree се използва, когато данните се съхраняват на диска, той намалява времето за достъп, като намалява височината на дървото и увеличава клоните в възела.
Друга разлика между B-дървото и бинарното дърво е, че B-дървото трябва да има всичките си дъщерни възли на едно и също ниво, докато двоичното дърво няма такова ограничение. Двоичното дърво може да има максимум 2 подребри или възли, докато в B-дърво може да има M няма подребри или възли, където M е редът на B-дървото.
- Сравнителна диаграма
- дефиниция
- Ключови разлики
- заключение
Сравнителна диаграма
| Основа за сравнение | B-дърво | Двоично дърво |
|---|---|---|
| Съществено ограничение | Един възел може да има най-много M брой на дочерните възли (където M е редът на дървото). | Един възел може да има максимум 2 броя подредове. |
| Използва се | Използва се, когато данните се съхраняват на диск. | Използва се, когато записи и данни се съхраняват в RAM. |
| Височина на дървото | дневникМ N (където m е редът на M-way tree) | дневник2 н |
| Приложение | Структура на данни за индексиране на кодове в много СУБД. | Оптимизация на кода, кодиране на Huffman и т.н. |
Определение на B-дърво
B-дърво е балансираното M-way дърво и известно още като дървото за балансирано сортиране. Подобно е на бинарното дърво за търсене, където възлите са организирани въз основа на вътрешно преминаване. Космическата сложност на B-дървото е O (n). Сложността на време за вмъкване и изтриване е O (log n).
Има някои условия, които трябва да важат за B-дърво:
- Височината на дървото трябва да лежи възможно най-малко.
- Над листата на дървото не трябва да има празни подребри.
- Листата на дървото трябва да дойдат на същото ниво.
- Всички възли трябва да имат най-малък брой деца, с изключение на оставяне на възли.
Свойства на B-дърво от ред M
- Всеки възел може да има максимален M брой деца и минимален M / 2 брой деца или произволен брой от 2 до максималния.
- Всеки възел има един ключ по-малко от децата с максимални клавиши M-1.
- Подреждането на клавишите е в някакъв определен ред в рамките на възлите. Всички ключове в поддървото, присъстващо отляво на клавиша, са предшественици на ключа, а тези, които присъстват вдясно на ключа, се наричат приемници.
- В момента на поставяне на пълен възел дървото се разделя на две части и ключът със средна стойност се вмъква в родителския възел.
- Операцията за сливане се извършва, когато възлите са изтрити.
Определение на Binary tree
Бинарното дърво е дървовидна структура, която може да има най-много два указателя за своите възли. Това означава, че най-високата степен, която един възел може да има, е 2 и също може да има нула или един градус.
Има определени варианти на двоично дърво, като строго бинарно дърво, пълно двоично дърво, разширено двоично дърво и т.н.
- Строго бинарното дърво е дърво, при което всеки нетерминален възел трябва да има ляво поддърво и дясно подтерево.
- Дърво се нарича цялостно бинарно дърво, когато то отговаря на условието да има 2 аз възли на всяко ниво, където i е нивото.
- Нишката на двоица е двоично дърво, което се състои или от 0 без възли, или от 2 броя възли.
Техники на преминаване
Обходът на дърво е една от най-честите операции, изпълнявани върху структурата на данните на дърветата, при която всеки възел е посетен точно веднъж по систематичен начин.
- Inorder - При това преминаване на дърво лявото поддърво се посещава рекурсивно, след това се посещава корен възел и в последното дясно поддърво се посещава.
- Preorer - В това преминаване на дърво кореновият възел се посещава първо, след това ляво подребрие и най-накрая дясно подребро.
- Пореден ред - Тази техника посещава лявото поддърво, след това дясното поддерево и най-после коренния възел.
- В B-дървото максималният брой на дъщерни възли, които може да има нетерминален възел, е M, където M е редът на B-дървото. От друга страна, бинарното дърво може да има най-много две подребри или дочерни възли.
- B-дърво се използва, когато данните се съхраняват на диск, докато двоичното дърво се използва, когато данните се съхраняват в бърза памет като RAM.
- Друга област на приложение за B-дърво е структурата на данните за индексиране на кода в СУБД, за разлика от тях, Бинарното дърво се използва при оптимизация на кодове, кодиране на Huffman и т.н.
- Максималната височина на B-дърво е логМN (M е редът на дървото). За разлика, максималната височина на двоичното дърво е лог2N (N е броят на възлите, а базата е 2, защото е за двоичен).
заключение
B-дървото се използва над бинарно и двоично дърво за търсене. Основната причина за това е йерархията на паметта, при която CPU е свързан към кеш с каналите с висока честотна лента, докато CPU е свързан към диска чрез канал с ниска честотна лента. Двоично дърво се използва, когато записите се съхраняват в RAM (малка и бърза), а B-дърво се използва, когато записите се съхраняват на диск (голям и бавен). Така че използването на B-tree вместо Binary tree значително намалява времето за достъп поради висок коефициент на разклоняване и намалена височина на дървото.
