Реферат: Создание эффективной реализации сортированного списка с использованием generics
Таким образом можно убить сразу двух зайцев – сохранить скорость поиска и резко увеличить скорость вставки.
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.
|
internal class PageBase { public int Count; } |
Описание страницы, находящейся на нулевом уровне:
|
internal class LeafPage<K, V> : PageBase { public KeyValuePair<K, V>[] PageItems; // массивэлементов public LeafPage<K, V> PriorPage; // ссылканапредыдущуюстраницу public LeafPage<K, V> NextPage; // ссылка на следующую страницу public LeafPage() { Count = 0; PageItems = new KeyValuePair<K, V>[BTConst.MaxCount]; К-во Просмотров: 524
Бесплатно скачать Реферат: Создание эффективной реализации сортированного списка с использованием generics
|