Головна

B-дерева: принципи побудови, операція пошуку.

  1.  I. Нові принципи кримінального права
  2.  I. Фундаментальні принципи
  3.  SMART-ПРИНЦИПИ МЕНЕДЖМЕНТУ
  4.  А) Д -47423 А Вимоги іншими операціями
  5.  Абстракція (від лат. Abstractio - відволікання) -операція відображення окремих суттєвих в будь-якому відношенні властивостей явищ.
  6.  Б) найкраща операція для лікування даного захворювання за сучасними науковими даними;

При збільшенні числа блоків, зайнятих індексом в розріджених індексованих файлах, знижується ефективність роботи. Структура, яка називається В-деревом, дозволяє уникнути такого зниження шляхом побудови індексу для індексу, і при необхідності далі, поки верхній індекси не буде поміщатися в один блок. Таким чином, виходить ієрархічна структура індексів - малюнок 10.

Малюнок 10 - В-дерево ступеня 5

В В-дереві вузол може мати багато синів (на практиці до тисячі). Кількість синів (максимальне) визначає ступінь В-дерева.

Вузол х, який зберігає n [x] ключів, має n [x] +1 синів. Що зберігаються в х ключі служать границями, що розділяють всіх нащадків вузла на n [x] +1 груп. За кожну групу відповідає один з синів х.

При організації По-дерев не повинно бути вузлів, заповнених менше, ніж наполовину. Структура В-дерева відрізняється від простої ієрархії індексів наступним угодою: в індексних блоках В-дерев значення ключів в першому записі пропускаються. При пошуку вважають, що всі значення, менші другого значення в індексі, покриваються відсутнім першим значенням ключа.

Пошук.

Нехай необхідно знайти запис із значенням ключа V. При цьому потрібно знайти шлях від кореня дерева до конкретного листа, в якому повинна знаходитися запис v, якщо вона існує в файлі. Пошук починається з кореня дерева і триває по ієрархії індексів, вибудовуючи шлях.



 Розріджені і щільні індекси. Індексація по декількох полях. |  Видалення.

 Оператор вибору SELECT |  Застосування агрегатних функцій і вкладених запитів в операторі вибору |  Оператори маніпулювання даними |  Фізична організація БД: файли, записи, блоки. |  Організація файлу БД у вигляді купи. Ефективність таких файлів. |  Хешировать файли: Бакет, каталог Бакета, додатковий каталог Бакета, вибір хеш-функції. Операції над хешировать файлами. |  Динамічне хешування. Операції над динамічно хешировать файлами. |  Послідовна організація файлів. Операції додавання і видалення записів в послідовних файлах, блок переповнення. |  Індексовані файли: ініціалізація, пошук. |  Індексовані файли: операції вставки і видалення записів. |

© um.co.ua - учбові матеріали та реферати