Рефераты | Рефераты по информатике, программированию | Создание эффективной реализации сортированного списка с использованием generics | страница реферата 2 | Большая Энциклопедия Рефератов от А до Я
Большая Энциклопедия Рефератов от А до Я
  • Рефераты, курсовые, шпаргалки, сочинения, изложения
  • Дипломы, диссертации, решебники, рассказы, тезисы
  • Конспекты, отчеты, доклады, контрольные работы

  • ПРИМЕЧАНИЕ

    Таким образом, при поиске нужной листовой страницы нет необходимости обращаться к ее содержимому:

    (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.

    internal class PageBase

    {

        public int Count;

    }


    Рекомендуем скачать другие рефераты по теме: сочинения по русскому языку, личные сообщения.



    Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9  10  11 |




    Поделитесь этой записью или добавьте в закладки

       




    Категории:



    Разделы сайта




    •