Алгоритми та структури даних · Senior · Запитання 14 з 75
Чому бази даних використовують для індексів B-дерева, а не бінарні дерева пошуку?
- 1Бінарні дерева не можуть ефективно зберігати рядкові ключі
- 2B-дерева витрачають менше процесора на порівняння, ніж BST
- ✓Правильна відповідь: Широкі вузли відповідають сторінкам диска, тож пошук читає мало сторінок
Пояснення
Вузол містить сотні ключів, тож дерево на мільйони рядків має лише 3-4 рівні, а кожен рівень - одне читання сторінки з диска. Бінарне дерево мало б близько 20 рівнів із поганою локальністю.