Структури індексації
Індексування – це процес зв’язування ключа з розташуванням відповідного запису даних в СУБД. Існує безліч структур індексування даних, використовуваних в базах даних NoSQL. B-Tree є однією з найпоширеніших структур індексу в СУБД. В ній внутрішні вузли можуть мати змінну кількість дочірніх вузлів у визначеному діапазоні.
Одне з основних відмінностей від інших деревоподібних структур, таких як AVL, полягає в тому, що B-Tree дозволяє мати змінну кількість дочірніх вузлів, що означає меншу балансування дерева, але більшу втрату простору. B + Tree – один з найпопулярніших варіантів B-дерев. Це поліпшення (на відміну від B-Tree) вимагає, щоб всі ключі знаходилися в листі.
Структура даних T-Trees була розроблена шляхом об’єднання функцій AVL-Дерева і B-Trees. Дерева AVL відносяться до типу самобалансирующихся дерев двійкового пошуку, тоді як дерева B – незбалансовані, а у кожного вузла може бути різна кількість дочірніх елементів.
В T-дереві структура дуже схожа на AVL-дерево і B-дерево. Кожен вузол зберігає кортежу {key-value, pointer}. Крім того, двійковий пошук використовується в поєднанні з декількома вузлами і кортежами, щоб забезпечити кращу пам’ять і продуктивність.
T-дерево має три типи вузлів: з правим і лівим дочірнім вузлом, кінцевий вузол без дочірніх вузлів і вузол з половинним листом тільки з одним дочірнім вузлом. Вважається, що у T-Trees краща загальна продуктивність.
