|
ПРИМЕЧАНИЕ
Таким образом, при поиске
нужной листовой страницы нет необходимости обращаться к ее содержимому:
(NodeArray[j].Key <= Key) AND (NodeArray[j + 1].Key > Key)
Таким образом можно убить
сразу двух зайцев – сохранить скорость поиска и резко увеличить скорость
вставки.
|
B+-деревья
Когда объем группировок начал подходить к миллионам
записей, этот алгоритм начал «тормозить» из-за увеличения размера массива
верхнего уровня. Проблемы с копированием больших объемов данных вернулись.
Чтобы избавиться от этой проблемы, можно применить тот же самый механизм, и
разбить массив верхнего уровня на несколько подмассивов. Это приведет к
созданию трехуровневого массива, а когда-нибудь, возможно, и четырехуровневого.
Так что в принципе есть резон сразу создавать универсальный алгоритм, автоматически увеличивающий количество уровней и строящий дерево. Структура этого
дерева включает страницы двух типов – узловые, содержащие массивы ссылок на
нижележащие страницы, и листовые, содержащие отсортированные списки данных.
Такое дерево называется B+-деревом. Однако разбирать подробно реализацию
B+-деревьев в этой статье я не буду.
Реализация двухуровневого массива
На практике в большинстве случаев достаточно
двухуровневых массивов. К тому же, их намного проще описывать. Они используют
те же подходы, что и в Б+-деревьях. Так что рассмотрим реализацию именно
двухуровневых массивов.
Вначале нужно определить структуру, которая будет
хранить пары ключ + значение (для листовых страниц) и ключ + ссылка на страницу
(для узловых страниц). В принципе, ссылку можно рассматривать как частный
случай данных. Так что с помощью generic-ов можно описать единую структуру. Вот
эта структура:
|
internal struct KeyValuePair<K, V>
{
internal K Key;
internal V Value;
public KeyValuePair(K key, V
value)
{
Key = key;
Value = value;
}
}
|
Определим класс PageBase, с единственным полем Count.
Главная