Версія від 08:28, 6 квітня 2021, створена Андрій Тищенко (Обговорити цю сторінку | внесок)
(різн.) ← Попередня версія | Поточна версія (різн.) | Новіша версія → (різн.)

Б-дерево

Б-де́рево, Бі-дерево (англ. B-tree) — структура даних, що являє собою збалансоване дерево пошуку з високим ступенем розгалуження.

Концепцію Б-дерева запропонували 1972 вчені в галузі інформаційних технологій Р. Байєр (нар. 1939; Німеччина) та Е. Маккрейт (нар. 1971; США) для оптимізації довільного доступу до великих обсягів даних.

Дерево пошуку збалансоване, якщо кількість з’єднань між листом і кореневим вузлом будь-яких двох його піддерев відрізняється не більше, ніж на 1. Високий ступінь розгалуження свідчить про те, що вузли дерева містять велику кількість ключових значень і, відповідно, мають велику кількість (від одиниць до тисяч) відгалужень (нащадків). Слід відрізняти Б-дерево від двійкового (бінарного) дерева, вузли якого мають не більше двох нащадків.

Б-дерева ефективні в роботі з даними, які зберігають на зовнішніх носіях, насамперед — на накопичувачах на магнітних дисках. Такі накопичувачі містять великі обсяги інформації за повільного доступу до неї.

Б-дерева широко використовують у системах управління базами даних, а також у файлових системах комп’ютерів.

Література

  1. Cormen T., Leiserson Ch., Rivest R. et al. Introduction to Algorithms. 3rd ed. Cambridge : MIT Press, 2009. P. 484–504.
  2. Knuth D. The Art of Computer Programming : in 5 vol. 2nd ed. Upper Saddle River : Addison-Wesley, 2012. Vol. 3. 782 p.
  3. 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/Б-дерево (дата звернення: 20.04.2021).


Оприлюднено

Статус гасла: Оприлюднено
Оприлюднено:
05.04.2021

Офіційний телеграм-канал ВУЕОфіційний телеграм-канал ВУЕ