Б-дерево
Б-де́рево, Бі-дерево (англ. B-tree) — структура даних, що являє собою збалансоване дерево пошуку з високим ступенем розгалуження.
Концепцію Б-дерева запропонували 1972 вчені в галузі інформаційних технологій Р. Баєр (нар. 1939; Німеччина) та Е. Мак-Крейт (нар. 1971; США) для оптимізації довільного доступу до великих обсягів даних.
Дерево пошуку збалансоване, якщо кількість з’єднань між листом і кореневим вузлом будь-яких двох його піддерев відрізняється не більше ніж на 1. Високий ступінь розгалуження свідчить про те, що вузли дерева містять велику кількість ключових значень і, відповідно, мають велику кількість (від одиниць до тисяч) відгалужень (нащадків). Слід відрізняти Б-дерево від двійкового (бінарного) дерева, вузли якого мають не більше двох нащадків.
Б-дерева ефективні в роботі з даними, які зберігають на зовнішніх носіях, насамперед — на накопичувачах на магнітних дисках. Такі накопичувачі містять великі обсяги інформації за повільного доступу до неї.
Б-дерева широко використовують у системах управління базами даних, а також у файлових системах комп’ютерів.
Література
- Cormen T., Leiserson Ch., Rivest R. et al. Introduction to Algorithms. 3rd ed. Cambridge : MIT Press, 2009. P. 484–504.
- Knuth D. The Art of Computer Programming : in 5 vol. 2nd ed. Upper Saddle River : Addison-Wesley, 2012. Vol. 3. 782 p.
- Petrov A. Database Internals: A Deep Dive Into How Distributed Data Systems Work. Sebastopol : O'Reilly Media, 2019. 350 p.
Автор ВУЕ
Покликання на цю статтю: Арістов О. В. Б-дерево // Велика українська енциклопедія. URL: https://vue.gov.ua/Б-дерево (дата звернення: 28.04.2024).
Статус гасла: Оприлюднено
Оприлюднено: 05.04.2021
Важливо!
Ворог не зупиняється у гібридній війні і постійно атакує наш інформаційний простір фейками.
Ми закликаємо послуговуватися інформацією лише з офіційних сторінок органів влади.
Збережіть собі офіційні сторінки Національної поліції України та обласних управлінь поліції, аби оперативно отримувати правдиву інформацію.
Отримуйте інформацію тільки з офіційних сайтів
Офіс Президента України
Верховна Рада України
Кабінет Міністрів України
Служба безпеки України
Міністерство оборони України
Міністерство внутрішніх справ України
