Внешний поиск

Индексно-последовательный доступ

Прямой подход к построению индекса заключается в сохранении массива c ключами и ссылками на элементы, упорядоченного по ключам, с последующим использованием бинарного поиска (см. ) для реализации операции найти. Для N элементов этот метод потребовал бы и , это значение можно считать практически постоянным. Например, если M= 1000, то logMN меньше 5 для всех N, меньших 1 триллиона.

На рис 16.1 приведен пример набора ключей, а на рис 16.2 — пример такой структуры дерева для этих ключей. Чтобы примеры были достаточно понятными, приходится использовать сравнительно небольшие значения M и N, но все же из этих примеров видно, что деревья для большого значения M будут плоскими.

Ключи (слева), используемые в примерах этой главы, представляют собой трехзначные восьмеричные числа, которые будут также интерпретироваться как 9-разрядные двоичные значения (справа).

Дерево на рис. 16.2 рис 16.2 является абстрактным представлением индекса, оно не зависит от устройства и похоже на множество других рассмотренных нами структур данных. Однако оно не особо отличается от зависящих от устройств индексов, которые можно встретить в программном обеспечении низкоуровневого доступа к дискам.

Например, в ряде ранних систем использовалась двухуровневая схема, в которой нижний уровень соответствовал элементам на страницах конкретного дискового устройства, а второй уровень — главному индексу отдельных устройств. В таких системах главный индекс хранился в оперативной памяти, поэтому для доступа к элементу с помощью такого индекса требовались две операции доступа: одна для чтения индекса и вторая для чтения страницы, содержащей элемент. С увеличением емкости дисков возрастали и размеры индексов, и для хранения индекса требовалось уже несколько страниц, что со временем привело к использованию иерархической схемы наподобие показанной на рис 16.2. Мы продолжим работать с абстрактным представлением, помня, что при необходимости оно может быть непосредственно реализовано с помощью типичного аппаратного и программного обеспечения низкого уровня.

Во многих современных системах аналогичная древовидная структура используется для организации очень больших файлов в виде последовательности дисковых страниц. Такие деревья не содержат ключей, но они могут эффективно поддерживать стандартные операции последовательного доступа к файлу, и (если каждый узел содержит счетчик размера его дерева) нахождения страницы, содержащей к-й элемент файла.

Поскольку метод индексации, показанный на рис 16.2, сочетает последовательную организацию ключей с индексным доступом, по историческим причинам он называется индексно-последовательным доступом (indexed sequential access). Этот метод удобен для приложений, в которых изменения в базе данных выполняются редко. Иногда сам индекс называют каталогом (directory). Недостаток использования индексно-последовательного доступа заключается в больших затратах на изменение каталога. Например, для добавления единственного ключа может потребоваться перестройка буквально всей базы данных с присвоением новых позиций многим ключам и новых значений индексам. Для преодоления этого недостатка и обеспечения возможности небольшого увеличения базы данных в ранних системах на дисках резервировались страницы переполнения, а в страницах — области переполнения; но все равно в динамических ситуациях такие технологии были не очень эффективны (см. упражнение 16.3). Методы, которые будут рассматриваться в разделах 16.3 и 16.4, обеспечивают надежные и эффективные альтернативы таким элементарным схемам.

В последовательном индексе ключи хранятся упорядоченными в полных страницах (справа), а индекс указывает на наименьший ключ в каждой странице (слева). При добавлении ключа требуется перестроить всю структуру данных.

Эти впечатляющие граничные значения позволяют смело принять, что на практике вряд ли встретится таблица символов, содержащая более 1030 элементов. Даже в такой неимоверно большой базе данных при 1000-путевом ветвлении элемент с заданным ключом можно найти с помощью менее 10 проб. И даже если бы как-то удалось записать информацию о каждом электроне во Вселенной, 1000-путевое ветвление позволило бы получить доступ к любому конкретному элементу с помощью менее 27 проб.

Мы не будем рассматривать реализации поиска и построения индексов подобного типа, поскольку они представляют собой специальные случаи более общих механизмов, рассматриваемых в следующем разделе (см. упражнение 16.17 и программу 16.2).

Упражнения

16.1. Составьте таблицу значений logM N для M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.2. Нарисуйте структуру индексно-последовательного файла для ключей 516, 177, 143, 632, 572, 161, 774, 470, 411, 706, 461, 612, 761, 474, 774, 635, 343, 461, 351, 4 30, 664, 127, 34 5, 171 и 357 при M= 5 и N= 6.

16.3. Предположим, что мы строим структуру индексно-последовательного файла для N элементов, со страницами емкостью M, но оставляем на каждой странице к свободных мест для возможного расширения. Приведите формулу для определения количества проб, необходимых для выполнения поиска, в виде функции от N, M и к. Используйте эту формулу для определения количества проб, необходимых для выполнения поиска при k = M/10, M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.4. Предположим, что затраты на одну пробу равны приблизительно а единиц времени, а средние затраты на поиск элемента на странице составляют приблизительно PM единиц времени. Найдите значение M, при котором затраты на поиск в структуре индексно-последовательного файла минимальны, при $$$\alpha / \beta =10, 100 {\ и\ } 1000$$$ и N= 103, 104, 105 и 106 .

B-деревья

Для построения структур поиска, которые могут быть эффективны в динамических ситуациях, мы будем строить многопутевые деревья, но при этом откажемся от ограничения, что каждый узел должен содержать точно M записей. Вместо этого выдвинем условие, что каждый узел должен иметь не более M записей, чтобы они помещались на странице, но узлы могут иметь и меньше записей. Чтобы гарантировать, что узлы имеют достаточное количество записей для обеспечения ветвления, необходимого для предотвращения увеличения длины путей, мы также потребуем, чтобы все узлы имели не менее (допустим) M/2 записей — за исключением, быть может, корня, который должен иметь не менее одной записи (двух ссылок). Причина этого исключения для корня станет понятна при подробном рассмотрении алгоритма построения. Байер (Bayer) и МакКрейт (McCreight) первыми (в 1970 г.) исследовали возможность использования многопутевых сбалансированных деревьев для внешнего поиска и назвали такие деревья B-деревьями. Термин B-дерево часто используется для описания именно той структуры данных, которая строится алгоритмом, предложенным Байером и МакКрейтом; мы же будем использовать его в качестве общего термина для обозначения семейства похожих алгоритмов.

Мы уже встречались с реализацией B-дерева: из определений 13.1 и 13.2 видно, что B-деревья четвертого порядка, в которых каждый узел содержит не более 4 и не менее 2 ссылок, являются ни чем иным, как сбалансированными 2-3-4-деревьями, описанными в . Лежащая в их основе абстракция допускает непосредственное обобщение, так что B-деревья можно реализовать, обобщив реализации нисходящего 2-3-4-дерева, описанные в . Однако различия между внешним и внутренним поиском, упомянутые в разделе 16.1, приводят к ряду различий в реализациях.

Два последних свойства в этом перечне несущественны, однако во многих ситуациях удобны и часто применяются в реализациях B-деревьев.

На . Обобщение очевидно: 4-узлы имеют три ключа и четыре ссылки, 5-узлы — четыре ключа и пять ссылок и т.д.: по одной ссылке для каждого возможного интервала ключей. Поиск начинается с корня и проходит от одного узла к другому, определяя в текущем узле интервал, который соответствуюет искомому ключу, и переходя к следующему узлу по соответствующей ссылке. Поиск завершается успешно, если ключ поиска находится в любом из рассмотренных узлов, и неудачно, если он дошел до низа дерева, не обнаружив искомый ключ. Как и в случае 2-3-4-деревьев, новый ключ можно вставить после выполнения поиска в нижнюю часть дерева, если при спуске вниз по дереву выполняется разбиение заполненных узлов: если корень является 8-узлом, он заменяется 2-узлом, связанным с двумя 4-узлами. Затем, каждый раз, когда встречается k-узел с присоединенным 8-узлом, он заменяется (к+1)-узлом с двумя присоединенными 4-узлами. Это правило гарантирует наличие места для вставки нового узла по достижении нижней части дерева.

Или же, как и в применительно к 2-3-4-деревьям, разбиение можно выполнять снизу вверх: после выполнения поиска новый ключ вставляется в нижний узел, если только тот не является 8-узлом — в этом случае он разбивается на два 4-узла со вставкой среднего ключа и двух ссылок в его родительский узел. Восходящее разбиение выполняется до тех пор, пока не встретится узел-предок, отличный от 8-узла.

Замена в предыдущих двух абзацах 4 на M/2, а 8 — на M позволяет преобразовать приведенные описания в описания поиска и вставки в М/2-...-М-деревьях для любого положительного четного M (см. упражнение 16.9).

На рисунке показано обобщение 2-3-4-деревьев, которое построено из узлов, содержащих от 4 до 8ссылок (и соответственно от 3 до 7ключей). Как и в случае 2-3-4-деревьев, мы поддерживаем высоту деревьев постоянной, разбивая встречающиеся 8-узлы при работе нисходящего или восходящего алгоритма вставки. Например, для вставки в это дерево еще одного ключа J нужно сначала разбить 8-узел на два 4-узла, а затем вставить ключ M в корень, преобразовав его в 6-узел. При разбиении корня возможно лишь создание нового корня, который будет 2-узлом — поэтому корень не подчиняется общему правилу, согласно которому узлы должны содержать не менее четырех ссылок.

Алгоритмы B-деревьев построены на основе этого базового набора абстракций. Как и в , существует значительная свобода в выборе конкретных представлений таких деревьев. Например, можно использовать расширенное RB-представление (см. упражнение 13.69). Для внешнего поиска мы используем еще более простое представление в виде упорядоченного массива, выбирая достаточно большое значение M, чтобы M-узлы заполняли всю страницу. Коэффициент ветвления равен по меньшей мере M/2, поэтому, как следует из текста после леммы 16.1, количество проб, необходимое для выполнения любого поиска или вставки, практически постоянно.

Вместо реализации только что описанного метода рассмотрим вариант, обобщающий стандартный индексный указатель, рассмотренный в разделе 16.1. Будем хранить ключи со ссылками на элементы во внешних страницах в нижней части дерева, а копии ключей со ссылками на страницы — во внутренних страницах. Мы вставляем новые элементы в нижнюю часть, а затем используем базовую абстракцию M/2-...-M дерева. Если страница содержит M записей, мы разбиваем ее на две страницы с M/2 записями в каждой и вставляем в родительскую страницу ссылку на новую страницу. При разбиении корня мы создаем новый корень с двумя дочерними узлами, тем самым увеличивая высоту дерева на 1.

На рис. 16.5 рис 16.7—16.7 показан процесс построения B-дерева вставками ключей, показанных на рис 16.1 (в приведенном порядке) в первоначально пустое дерево при M= 5.

Здесь показаны шесть вставок в первоначально пустое B-дерево, построенное из страниц, которые могут содержать пять ключей и ссылок, при использовании 3-значных восьмеричных ключей (9-разрядных двоичных чисел). Ключи в страницах хранятся по порядку. Шестая вставка приводит к разбиению на два внешних узла с тремя ключами в каждом и внутренний узел, служащий в качестве индекса: его первая запись указывает на страницу, содержащую все ключи, которые больше или равны 000, но меньше 601, а вторая запись — на страницу, содержащую все ключи, которые больше или равны 601.

После вставки четырех ключей обе внешние страницы оказываются заполненными (слева). Затем, при вставке ключа 2 7 5, первая страница разбивается с передачей ссылки на новую страницу (вместе с ее наименьшим ключом 37 3) вверх по индексу (в центре). Далее, при вставке ключа 7 37 разбивается нижняя страница, также с передачей ссылки на новую страницу вверх по индексу (справа).

Продолжая наш пример, мы вставляем 13 ключей . Разбиения узлов выполняются при вставке ключей 277 (слева), 526 (в центре) и 107 (справа). Разбиение узла, вызванное вставкой ключа 52 6, приводит также к разбиению индексной страницы и увеличению высоты дерева на единицу.

Выполнение вставок сводится лишь к добавлению элемента в страницу, но на основании структуры результирующего дерева можно определить важные события, происшедшие во время его построения. Дерево содержит семь внешних страниц, поэтому должно было быть выполнено шесть разбиений внешних узлов, и поскольку его высота равна 3, корень дерева должен был разбиваться дважды. Эти события описаны в подписях к рисункам.

В программе 16.1 приведены определения типов для узлов нашей реализации B-дерева. Мы не указываем подробно структуру узлов, как в рабочей реализации, т.к. для этого потребовались бы ссылки на конкретные страницы диска. Для простоты мы используем один тип узлов, каждый узел состоит из массива записей, а каждая запись содержит элемент, ключ и ссылку. Каждый узел содержит также счетчик активных записей. Мы не обращаемся к элементам во внутренних узлах, не обращаемся к ссылкам во внешних узлах, и не обращаемся к ключам в элементах дерева. При использовании конкретной структуры данных в реальном приложении можно сэкономить память с помощью конструкций наподобие union или производных классов. Можно было бы также сэкономить память ценой увеличения времени выполнения, используя везде в дереве вместо ключей ссылки на элементы. Такие конструктивные решения достигаются очевидными изменениями кода и зависят от конкретного характера ключей, элементов и ссылок в приложении.

С помощью этих определений и рассмотренных примеров деревьев, код выполнения операции найти, приведенный в программе 16.2, реализуется элементарно. Для внешних узлов мы просматриваем массив узлов, чтобы найти ключ, соответствующий искомому ключу, и возвращаем связанный с ним элемент, если поиск успешен, и пустой элемент, если неудачен. Для внутренних узлов мы просматриваем массив узлов, чтобы найти ссылку на уникальное поддерево, которое может содержать искомый ключ.

Программа 16.3 является реализацией операции вставить для B-деревьев; в ней также применяется рекурсивный подход, используемый во многих других реализациях деревьев поиска из глав 13 и 15. Эта реализация является восходящей, т.к. проверка, нужно ли разбивать узел, выполняется после рекурсивного вызова — поэтому первым разбивается внешний узел. Разбиение требует передачи новой ссылки наверх к родительскому узлу разбиваемого узла, который, в свою очередь, может нуждаться в разбиении и передаче ссылки его родительскому узлу и т.д. — возможно, вплоть до корня дерева (при разбиении корня создается новый корень с двумя дочерними поддеревьями).

В противоположность этому в реализации 2-3-4-дерева в программе 13.6 проверка, нужно ли разбивать узел, выполняется перед рекурсивным вызовом, и поэтому разбиение выполняется при спуске вниз по дереву. Для B-деревьев можно воспользоваться и нисходящим подходом (см. упражнение 16.10). Во многих приложениях, использующих B-деревья, это различие между нисходящим и восходящим подходами несущественно, поскольку такие деревья являются очень плоскими.

Код разбиения узла приведен в программе 16.4. В нем переменная M должна иметь четное значение, и каждый узел дерева может содержать только M — 1 элемент. Этот подход позволяет вставлять M-й элемент в узел перед разбиением этого узла и значительно упрощает код, не оказывая особого влияния на затраты (см. упражнения 16.20 и 16.21). Для простоты аналитических выкладок, приведенных далее в этом разделе, мы вводим ограничение, что количество элементов каждого узла должно быть не больше M; реальные различия несущественны. В нисходящей реализации эта технология не нужна, т.к. в ней наличие свободного места в каждом узле для вставки нового ключа обеспечивается автоматически.

Программа 16.1. Определения типов узлов B-дерева

Каждый узел в B-дереве содержит массив и счетчик количества активных записей в этом массиве. Каждая запись массива представляет собой ключ, элемент и ссылку на узел. Во внутренних узлах используются только ключи и ссылки; во внешних узлах используются только ключи и элементы. Новые узлы создаются пустыми, для чего обнуляется поле счетчика.

  template <class Item, class Key>
  struct entry
    { Key key; Item item; struct node *next; };
  struct node
    { int m; entry<Item, Key> b[M];
      node() { m = 0; }
    };
  typedef node *link;
      

Программа 16.2. Поиск в B-дереве

Как обычно, эта реализация операции найти для B-деревьев выполнена рекурсивной. Для внутренних узлов (имеющих положительную высоту) выполняется поиск ключа, который больше искомого, а затем рекурсивный вызов для поддерева, указанного предыдущей ссылкой. Для внешних узлов (высота которых равно 0) выполняется просмотр, чтобы выяснить, содержат ли они элемент с ключом, равным искомому.

private:
  Item searchR(link h, Key v, int ht)
    { int j;
      if ( ht == 0)
        for (j = 0; j < h->m; j++)
          { if (v == h->b[j].key)
            return h->b[j].item;
          }
      else
        for (j = 0; j < h->m; j++)
          if ((j + 1 == h->m) || (v < h->b[j + 1].key))
            return searchR(h->b[j].next, v, ht-1);
      return nullItem;
    }
public:
  Item search(Key v)
    { return searchR(head, v, HT); }
      

Программа 16.3. Вставка в B-дерево

При вставке новых элементов большие элементы сдвигаются вправо на одну позицию, как в сортировке вставками. Если вставка приводит к переполнению узла, вызывается функция split для разбиения узла пополам, а затем ссылка на новый узел вставляется во внутренний родительский узел, который также может потребовать разбиения; таким образом, влияние вставки может распространиться вплоть до корня.

private:
  link insertR(link h, Item x, int ht)
    { int i, j; Key v = x.key(); entry<Item, Key> t;
      t.key = v; t.item = x;
      if (ht == 0)
        for (j = 0; j < h->m; j++)
          { if (v < h->b[j].key) break; }
      else
        for (j = 0; j < h->m; j++)
          if ((j+1 == h->m) || (v < h->b[j+1].key))
            { link u;
              u = insertR(h->b[j++].next, x, ht-1);
              if (u == 0) return 0;
              t.key = u->b[0].key; t.next = u; break;
            }
      for (i = h->m; i > j; i—) h->b[i] = h->b[i-1];
      h->b[j] = t;
      if (++h->m < M) return 0; else return split(h);
    }
public:
  ST(int maxN)
    { N = 0; HT = 0; head = new node; }
  void insert(Item item)
    { link u = insertR(head, item, HT);
      if (u == 0) return;
      link t = new node(); t->m = 2;
      t->b[0].key = head->b[0].key;
      t->b[1].key = u->b[0].key;
      t->b[0].next = head;
      t->b[1].next = u;
      head = t; HT++;
    }
      

Программа 16.4. Разбиение узла B-дерева

Для разбиения узла в B-дереве создается новый узел, и большая половина ключей перемещается в новый узел, а затем корректируются счетчики, и в середины обоих узлов заносятся сигнальные ключи. В этой программе предполагается, что M четно, а в каждом узле имеется лишняя позиция для элемента, вызвавшего разбиение. То есть максимальное количество ключей в узле равно M-1, а когда количество ключей в узле достигает M, он разбивается на два узла с M/2 ключами в каждом.

  link split(link h)
    { link t = new node();
      for (int j = 0; j < M/2; j++)
        t->b[j] = h->b[M/2+j];
      h->m = M/2; t->m = M/2;
      return t;
    }
      

Если M равно 1000, то при N, меньшем 125 миллионов, высота дерева меньше трех. В типичных ситуациях можно хранить корневой узел в оперативной памяти и этим уменьшить затраты до двух проб. Для реализаций поиска на диске этот шаг можно предпринимать явно перед запуском любого приложения, связанного с очень большим количеством поисков; в виртуальной памяти с кэшированием корневым узлом будет узел, который вероятнее всего находится в быстрой памяти, т.к. это узел, к которому происходит наибольшее количество обращений.

Вряд ли можно рассчитывать на реализацию поиска, которая сможет гарантировать выполнение менее двух проб для выполнения операций найти и вставить в очень больших файлах, и B-деревья находят широкое применение, поскольку они позволяют приблизиться к этому идеалу. Однако производительность и гибкость достигаются ценой неиспользуемой памяти внутри узлов, что для очень больших файлов может оказаться обременительным.

Лемму 16.3 можно также проверить, написав программу для моделирования вероятностного процесса (см. упражнение 16.11 и рис 16.8 и 16.9). Конечно, можно также просто строить случайные B-деревья и измерять их структурные характеристики. Вероятностное моделирование выполнить проще, чем провести математический анализ или создать полную реализацию, кроме того, оно служит важным инструментом изучения и сравнения вариантов алгоритмов (см., например, упражнение 16.16).

Реализации других операций такой таблицы символов аналогичны соответствующим реализациям для других ранее рассмотренных представлений с использованием деревьев и оставлены в качестве упражнений (см. упражнения 16.22—16.25). В частности, реализации операций выбрать и сортировать очевидны, но, как обычно, правильная реализация операции удалить может оказаться сложной задачей. Подобно операции вставить, большинство операций удалить сводятся к простому удалению элемента из внешней страницы и уменьшению значения ее счетчика; но что делать, если необходимо удалить элемент из узла, который имеет только M/2 элементов? Естественный подход — найти для заполнения свободного места элементы в родственных узлах (возможно, с уменьшением количества узлов на единицу), но тогда реализация усложняется, поскольку приходится отслеживать ключи, связанные со всеми перемещаемыми по узлам элементами.

Здесь показано моделирование процесса вставок элементов со случайными ключами в первоначально пустое B-дерево со страницами, которые могут содержать девять ключей и ссылок. Каждая линия соответствует всем внешним узлам, а каждый отдельный узел изображается отрезком этой линии, длина которого пропорциональна количеству элементов в данном узле. Большинство вставок выполняется в незаполненных внешних узлах, что приводит к увеличению их размера на 1. Если вставка выполняется в заполненном внешнем узле, он разбивается на два узла половинного размера.

В этой версии рис 16.8 показано заполнение страниц во время роста B-дерева. Как и в предыдущем случае, большинство вставок приходится на не заполненные страницы, лишь увеличивая их заполнение на 1. Когда вставка приходится на полную страницу, страница разбивается на две полупустые страницы.

В реальных ситуациях обычно можно использовать значительно более простой подход, оставляя внешние узлы незаполненными, что не особенно снижает производительность (см. упражнение 16.25).

Сразу же приходит на ум множество вариантов базовой абстракции B-дерева. Один класс вариантов позволяет экономить время за счет упаковки во внутренние узлы максимально возможного количества ссылок на страницы, в результате чего повышается коэффициент ветвления, и дерево становится более плоским. Как уже отмечалось, в современных системах преимущества, получаемые в результате таких изменений, несущественны, поскольку стандартные значения параметров позволяют реализовать операции найти и вставить всего за две пробы — такую эффективность вряд ли удастся повысить. Другой класс вариантов повышает эффективность использования дисковой памяти, объединяя перед разбиением узлы с их родственными узлами.

Упражнения 16.13—16.16 посвящены такому методу, который при работе со случайными ключами позволяет уменьшить излишние затраты дисковой памяти с 44 до 23%. Как обычно, выбор того или иного варианта зависит от свойств приложения. В силу наличия множества различных ситуаций, в которых применимы B-деревья, мы не будем подробно рассматривать эти вопросы. Мы не сможем также рассмотреть подробности реализаций, поскольку это потребовало бы учета слишком многих факторов, зависящих от устройств и систем. Как обычно, детальная разработка таких приложений — рискованное дело, и в современных системах желательно избегать наличия столь прихотливого и не переносимого кода, особенно если базовый алгоритм работает вполне успешно.

Упражнения

16.5. Приведите содержимое 3-4-5-6-дерева, образованного вставками ключей E A S Y Q U E S T I O N W I T H P L E N T Y O F K E Y S в указанном порядке в первоначально пустое дерево.

16.6. Постройте рисунки наподобие рис 16.7, иллюстрирующие процесс вставки ключей 516, 177, 143, 632, 572, 161, 774, 470, 411, 706, 461, 612, 761, 474, 774, 635, 343, 461, 351, 430, 664, 127, 345, 171 и 357 в указанном порядке в первоначально пустое дерево при M= 5.

16.7. Приведите высоту B-деревьев, образованных вставками ключей из упражнения 16.6 в указанном порядке в первоначально пустое дерево для каждого значения M > 2.

16.8. Нарисуйте B-дерево, образованное вставками 16 одинаковых ключей в первоначально пустое дерево при M= 4.

16.9. Нарисуйте 1-2-дерево, образованное вставками ключей E A S Y Q U E S T I O N в первоначально пустое дерево. Объясните, почему 1-2-деревья не представляют практического интереса как сбалансированные деревья.

16.10. Измените реализацию вставки в B-дерево, приведенную в программе 16.3, чтобы разбиение в ней выполнялось при спуске вниз по дереву, аналогично реализации вставки в 2-3-4-дерево (программа 13.6).

16.11. Напишите программу для вычисления среднего количества внешних страниц B-дерева порядка M, построенного N случайными вставками в первоначально пустое дерево при использовании вероятностного процесса, описанного после леммы 16.1. Выполните программу для M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.12. Предположим, что в трехуровневом дереве а ссылок могут храниться во внутренней памяти, от b до 2b ссылок — в страницах, представляющих внутренние узлы, и от с до 2с элементов — в страницах, представляющих внешние узлы. Представьте максимальное количество элементов, которое может храниться в таком дереве, в виде функции от a, b и с.

16.13. Рассмотрите эвристику родственного разбиения B-деревьев (или B*-дерево): когда требуется разбить узел, содержащий M записей, мы объединяем этот узел с его родственным узлом. Если родственный узел содержит к записей, при к < M— 1, мы перераспределяем элементы, помещая и в родственный, и в полный узел приблизительно по (M + к)/2 записей. В противном случае мы создаем новый узел и помещаем в каждый узел дерева приблизительно по 2M/3 записей. Кроме того, мы позволяем корню расти до размера около 4M/3, разбивая его и создавая новый корневой узел с двумя записями, когда его размер достигает этого предельного значения. Укажите границы количества проб, используемых для выполнения поиска или вставки в B*-дереве порядка M, содержащем N элементов. Сравните эти границы с соответствующими границами для B-деревьев (см. лемму 16.2) при M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.14. Разработайте реализацию операции вставить для B*-дерева (основанную на

эвристике родственного разбиения) (см. упражнение 16.13).

16.15. Создайте рисунок, аналогичный рис 16.8, для иллюстрации эвристики родственного разбиения (см. упражнение 16.13).

16.16. Выполните вероятностное моделирование (см. упражнение 16.11) для определения среднего количества страниц, задействованных при использовании эвристики родственного разбиения (см. упражнение 16.13) для построения B*-дерева порядка M вставками случайных узлов в первоначально пустое дерево, при M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.17. Напишите программу для восходящего построения индекса B-дерева, начиная с массива ссылок на страницы, содержащих от M до 2M упорядоченных элементов.

16.18. Можно ли построить индекс со всеми заполненными страницами, как на рис 16.2, с помощью алгоритма вставки в B-дерево, рассмотренного в тексте (программа 16.3)? Обоснуйте свой ответ.

16.19. Предположим, что несколько различных компьютеров имеют доступ к одному и тому же индексу, и поэтому несколько программ практически одновременно могут попытаться вставить новый узел в одно и то же B-дерево. Объясните, почему в такой ситуации нисходящие B-деревья могут оказаться лучше восходящих. Считайте, что каждая программа может удержать (и удерживает) другие программы от модификации любого заданного узла, который она считала в память и может впоследствии изменить.

16.20. Измените реализацию B-дерева в программах 16.1—16.3, чтобы один узел дерева мог содержать M элементов.

16.21. Постройте таблицу значений разностей log999N и logi000N для N= 103, 104, 105 и 106 .

16.22. Реализуйте операцию сортировать для таблицы символов на основе B-дерева.

16.23. Реализуйте операцию выбрать для таблицы символов на основе B-дерева.

16.24. Реализуйте операцию удалить для таблицы символов на основе B-дерева.

16.25. Реализуйте операцию удалить для таблицы символов на основе B-дерева, используя простой метод, когда указанный элемент удаляется из внешней страницы (возможно, количество элементов в этой странице станет меньше M/2), но изменение не распространяется вверх по дереву, за исключением, возможно, коррекции значений ключей, если удаленный элемент был наименьшим в своей странице.

16.26. Измените программы 16.2 и 16.3, чтобы внутри узлов применялся бинарный поиск (см. программу 12.6). Определите значение M, которое минимизирует время, затрачиваемое программой на построение таблицы символов вставками N элементов со случайными ключами в первоначально пустую таблицу, при N= 103, 104, 105 и 106 . Сравните полученные значения времени с соответствующими значениями для RB-деревьев (программа 13.6).

Расширяемое хеширование

Альтернатива B-деревьям, распространяющая применение алгоритмов поразрядного поиска на внешний поиск, была разработана в 1978 г. Фагином (Fagin), Нивергельтом (Nievergelt), Пиппенгером (Pippenger) и Стронгом (Strong). Их метод, названный расширяемым хешированием (extendible hashing), приводит к реализации операции найти, требующей в типичных приложениях всего одной-двух проб. Для соответствующей реализации операции вставить также (почти всегда) нужны лишь одна-две пробы.

Расширяемое хеширование сочетает свойства методов хеширования, алгоритмов на основе многопутевых trie-деревьев и методов последовательного доступа. Подобно методам хеширования, описанным в , расширяемое хеширование представляет собой рандомизированный алгоритм — поэтому сначала необходимо определить хеш-функцию, которая преобразует ключи в целые числа (см. раздел 14.1 ). Для простоты в этом разделе мы будем просто считать, что ключи являются случайными битовыми строками фиксированной длины. Подобно алгоритмам с использованием многопутевых trie-деревьев из , расширяемое хеширование начинает поиск, используя ведущие разряды ключей в качестве индексных указателей в таблице, размер которой равен степени 2. Подобно алгоритмам на основе B-деревьев, при использовании расширяемого хеширования элементы хранятся в страницах, которые при заполнении разбиваются на две части. Подобно методам индексно-последовательного доступа, расширяемое хеширование поддерживает каталог, указывающий, где можно найти страницу, в которой находятся соответствующие искомому ключу элементы. Сочетая эти знакомые свойства в одном алгоритме, расширяемое хеширование как нельзя более подходит для завершения знакомства с алгоритмами поиска.

Предположим, что количество доступных страниц диска является степенью 2 — скажем, 2^d. Тогда можно поддерживать каталог 2^d различных ссылок на страницы, использовать d разрядов ключей для индексного доступа к этому каталогу и хранить в одной и той же странице все ключи, первые к разрядов которых совпадают (см. рис 16.10). Как и в случае B-деревьев, элементы на страницах хранятся упорядоченными, и, найдя страницу, которая соответствует элементу с заданным искомым ключом, мы выполняем в ней последовательный поиск.

На рис 16.10 приведены две базовых концепции, лежащие в основе расширяемого хеширования. Во-первых, совсем не обязательно поддерживать 2^d страниц. То есть можно иметь несколько записей каталога со ссылками на одну и ту же страницу, объединив на одной странице ключи с различными значениями, первые d разрядов которых совпадают.

Каталог, состоящий из восьми записей, позволяет содержать до 40 ключей, храня все записи с первыми 3 совпадающими разрядами на одной странице, обратиться к которой можно через ссылку, хранящуюся в каталоге (слева). Запись 0 каталога содержит ссылку на страницу, которая содержит все ключи, начинающиеся с 000; запись 1 таблицы содержит ссылку на страницу, которая содержит все ключи, начинающиеся с 001; запись 2 таблицы содержит ссылку на страницу, которая содержит все ключи, начинающиеся с 010, и т.д. Если некоторые страницы заполнены не полностью, количество требуемых страниц можно уменьшить, используя несколько ссылок на одну и ту же страницу. В данном примере (слева) ключ 3 73 находится на той же странице, что и ключи, начинающиеся с 2; эта страница определена как содержащая элементы с ключами, первые два разряда которых равны 01.

Если удвоить размер каталога и скопировать каждую ссылку, то получим структуру, которую можно индексировать первыми 4 разрядами искомого ключа (справа). Например, последняя страница по-прежнему определяется как содержащая элементы с ключами, первые три разряда которых равны 111, и она будет доступна через каталог для искомых ключей с первыми 4 разрядами 1110 или 1111. Этот больший каталог допускает увеличение таблицы.

Это не помешает быстро выполнять поиск в структуре и в то же время позволяет находить страницу с искомым ключом, используя ведущие разряды ключа для индексного доступа к каталогу. Во-вторых, для увеличения емкости таблицы можно удваивать размер каталога.

В частности, структура данных, которая применяется для расширяемого хеширования, значительно проще используемой в B-деревьях. Она состоит из страниц, содержащих до M элементов, и каталога с 2^d ссылками на страницы (см. программу 16.5). Ссылка в ячейке каталога x указывает на страницу, содержащую все элементы с ведущими d разрядами, равными х. Значение d выбирается достаточно большим, чтобы в каждой странице гарантированно хранилось менее M элементов. Реализация операции найти проста: мы используем ведущие d разрядов ключа для индексного доступа к каталогу, что обеспечивает доступ к странице, которая содержит все элементы с соответствующими ключами, а затем выполняем последовательный поиск такого элемента на данной странице (см. программу 16.6).

Для поддержки операции вставить структура данных должна быть несколько более сложной, однако одно из ее свойств заключается в том, что этот алгоритм поиска успешно работает без каких-либо модификаций. Но сначала необходимо ответить на следующие вопросы:

Программа 16.5. Структуры данных для расширяемого хеширования

Расширяемая хеш-таблица — это каталог ссылок на страницы (подобно внешним узлам в B-деревьях), которые содержат до 2M элементов. Каждая страница содержит также счетчик (m) количества элементов в странице и целое число (k), задающее количество ведущих разрядов, которые должны совпадать в ключах элементов. Как обычно, N — количество элементов в таблице. Переменная d задает количество разрядов, которые используются для индексации в каталоге, а D — количество записей в каталоге; таким образом, D = 2d . Вначале таблица создается соответствующей каталогу размером 1, со ссылкой на пустую страницу.

template <class Item, class Key>
class ST
  { private:
      struct node
        { int m; Item b[M]; int k;
          node() { m = 0; k = 0; }
        } ;
      typedef node *link;
      link* dir;
      Item nullItem;
      int N, d, D;
     public:
       ST(int maxN)
         { N = 0; d = 0; D = 1;
           dir = new link[D];
           dir[0] = new node;
         }
  } ;
      

Программа 16.6. Поиск в таблице расширяемого хеширования

Поиск в таблице расширяемого хеширования сводится лишь к использованию ведущих разрядов ключа для индексного доступа к каталогу и выполнению на указанной странице последовательного поиска элемента, ключ которого равен искомому. Единственное выдвигаемое при этом требование — каждая запись каталога должна указывать на страницу, которая гарантированно содержит все элементы таблицы символов, начинающиеся с указанных разрядов.

  private:
    Item search(link h, Key v)
    { for (int j = 0; j < h->m; j++)
      if (v == h->b[j].key()) return h->b[j];
      return nullItem;
    }
  public:
    Item search(Key v)
      { return search(dir[bits(v, 0, d)], v); }
      

Например, в примере, приведенном на рис 16.10, нельзя использовать d = 2, поскольку некоторые страницы окажутся переполненными, и нельзя использовать d = 5, поскольку слишком много страниц будут пустыми. Как обычно, наибольший интерес вызывает поддержка операции вставить для АТД таблицы символов, чтобы, например, структура могла постепенно разрастаться по мере выполнения ряда чередующихся операций найти и вставить. Принятие такой точки зрения соответствует уточнению первого вопроса:

Например, в примере на рис 16.10 нельзя вставить элемент, ключ которого начинается с 5 или 7, поскольку соответствующие страницы заполнены.

Некоторые d-разрядные последовательности могут не появляться ни в одном из ключей. В определении 16.3 никак не упомянуты соответствующие записи каталога, хотя существует естественный способ организации ссылок на пустые страницы, который будет рассмотрен чуть ниже.

Для поддержания этих характеристик при разрастании таблицы мы используем две базовые операции: разбиение страницы, при котором некоторые ключи с полной страницы переносятся на другую страницу, и разбиение каталога, при котором размер каталога удваивается, а значение d увеличивается на 1. А именно, при заполнении страницы мы разбиваем ее на две, используя для определения элементов, которые должны быть перемещены на новую страницу, самый левый разряд, которым различаются ключи,. При разбиении страницы соответствующим образом корректируются записи каталога, а при необходимости его размер удваивается.

Как обычно, лучший способ понять алгоритм — это проследить его работу при вставке набора ключей в первоначально пустую таблицу. Каждая из ситуаций, которые должен обрабатывать алгоритм, проявляется в начале процесса в простейшей форме, и принципы, лежащие в основе алгоритма, вскоре становятся понятными.

На рис 16.13—16.13 показано построение расширяемой хеш-таблицы для набора 25 восьмеричных ключей, рассматриваемого в этой главе. Как и в B-деревьях, большинство вставок не приводят к переполнению: они просто добавляют ключ в страницу. Поскольку процесс начинается с одной страницы, а завершается восемью, можно сделать вывод, что семь вставок вызвали разбиение страниц. Поскольку в начале размер каталога равен 1, а в конце — 16, можно сделать вывод, что четыре вставки привели к разбиению каталога.

Как и в B-деревьях, первые пять вставок в расширяемую хеш-таблицу приходятся на одну страницу (слева). Затем, при вставке ключа 773, выполняется разбиение на две страницы (одна содержит все ключи, начинающиеся с бита 0, другая — все ключи, начинающиеся с бита 1), а размер каталога удваивается, чтобы он содержал по одному указателю на каждую из страниц (в центре). Ключ 742 вставляется в нижнюю страницу (т.к. он начинается с бита 1), а ключ 373 — в верхнюю страницу (т.к. он начинается с бита 0), но затем нижнюю страницу приходится разбить, чтобы было куда поместить ключ 52 4. Для выполнения этого разбиения все элементы, ключи которых начинаются с битов 10, помещаются на одну страницу, а все элементы, ключи которых начинаются с битов 11 — на другую, и размер каталога снова удваивается, чтобы в нем могли поместиться указатели на обе эти страницы (справа). Каталог содержит две ссылки на страницу, содержащую элементы с ключами, которые начинаются с бита 0: одна для ключей, которые начинаются с битов 00, и другая для ключей, которые начинаются с битов 01.

Программа 16.7 является реализацией операции вставить для расширяемой хеш-таблицы. Сначала, как и при поиске, с помощью единственного обращения к каталогу мы находим страницу, которая может содержать искомый ключ. Затем мы вставляем в нее новый элемент, как это делалось для внешних узлов в B-деревьях (см. программу 16.2). Если в результате этой вставки в узле оказывается M элементов, вызывается функция разбиения — опять же, как и для B-деревьев, правда, на этот раз она сложнее. Каждая страница содержит число к ведущих разрядов, которые совпадают в ключах всех элементов на этой странице, и, поскольку разряды нумеруются слева направо, начиная с 0, к задает также индекс разряда, который необходимо проверить для определения способа разбиения элементов.

Ключи 766 и 275 вставляются в крайнее правое B-дерево, показанное на рис 16.11, без разбиения узлов (слева). Затем, при вставке ключа 737, нижняя страницаразбивается, и, поскольку существует только одна ссылка на нижнюю страницу, это приводит кразбиению каталога (в центре). Затем выполняется вставка ключей 574, 434, 641 и 207, после чего необходимо разбиение верхней страницы (справа).

Продолжая пример, приведенный на рис 16.11 и 16.12, мы вставляем 5 ключей . Разбиение узлов происходит при вставке ключей 526 (слева) и 107 (справа).

Программа 16.7. Вставка в расширяемую хеш-таблицу

Чтобы вставить элемент в расширяемую хеш-таблицу, мы выполняем его поиск, а затем вставляем элемент в найденную страницу (и разбиваем ее, если вставка вызывает переполнение). Общая схема не отличается от используемой для B-деревьев, но алгоритмы поиска и разбиения иные. Функция разбиения создает новый узел, затем проверяет к-й бит (считая слева) ключа каждого элемента: если этот бит равен 0, элемент остается в старом узле; если 1 — перемещается в новый. В поле " количество одинаковых ведущих разрядов " обоих узлов после разбиения заносится значение к + 1. Если этот процесс не приводит к наличию по меньшей мере одного ключа в каждом узле, разбиение выполняется снова, пока элементы не станут разделены. И, наконец, мы вставляем ссылку на новый узел в каталог.

  private:
    void split(link h)
      { link t = new node;
        while (h->m == 0 || h->m == M)
          { h->m = t->m = 0; 
            for (int j = 0; j < M; j++)
              if (bits(h->b[j].key(), h->k, 1) == 0)
                h->b[h->m++] = h->b[j];
            else
              t->b[t->m++] = h->b[j];
            t->k = ++(h->k);
          }
        insertDIR(t, t->k);
      }
    void insert(link h, Item x)
    { int j; Key v = x.key();
      for (j = 0; j < h->m; j++)
        if (v < h->b[j].key()) break;
      for (int i = (h->m)++; i > j; i—-)
        h->b[i] = h->b[i-1];
      h->b[j] = x;
      if (h->m == M) split(h);
    }
  public:
    void insert(Item x)
      { insert(dir[bits(x.key(), 0, d)], x); }
      

Следовательно, для разбиения страницы мы создаем новую страницу, затем помещаем все элементы, для которых данный разряд равен 0, в старую страницу, а все элементы, для которых он равен 1 — в новую страницу, а затем для обеих страниц устанавливаем значение счетчика разрядов равным к + 1. Вообще-то возможен случай, когда в полном узле все ключи имеют одинаковое значение разряда к. В этом случае нужно просто перейти к следующему разряду и продолжать этот процесс до тех пор, пока каждая страница не будет содержать по меньшей мере один элемент. Однажды этот процесс должен завершиться, если только не имеется M значений одного и того же ключа. Вскоре мы рассмотрим и этот случай.

Как и в случае B-деревьев, на каждой странице резервируется свободное место для одной лишней записи, которая позволяет выполнять разбиение после вставки — это упрощает код. Данный прием почти не влияет на производительность, так что при анализе им можно пренебречь.

При создании новой страницы необходимо вставить в каталог ссылку на нее. Код, выполняющий эту вставку, приведен в программе 16.8. Простейшим является случай, когда перед вставкой каталог содержит ровно две ссылки на страницу, которая будет разбита. В этом случае нужно лишь записать вторую ссылку, указывающую на новую страницу. Если количество разрядов к, которое нужно для различения ключей на новой странице, превышает количество разрядов d для доступа к каталогу, то размер каталога нужно увеличить, чтобы в нем могла поместиться новая запись. И, наконец, выполняется соответствующее изменение ссылок в каталоге.

Если более M элементов имеют одинаковые ключи, таблица переполняется, и программа 16.7 зацикливается, пытаясь различить эти ключи. Есть еще одна похожая проблема: каталог может оказаться неоправданно большим, если ключи имеют очень много совпадающих ведущих разрядов. Эта ситуация похожа на излишнее время, требуемое для выполнения MSD-сортировки файлов с большим количеством одинаковых ключей или длинными последовательностями разрядов, в которых они совпадают. Решение этих проблем зависит от рандомизации, обеспечиваемой хеш-функцией (см. упражнение 16.43). Но даже при использовании хеширования в случае большого количества одинаковых ключей приходится предпринимать специальные действия, поскольку хеш-функции отображают равные ключи в равные хеш-значения. Повторяющиеся ключи могут сделать каталог неестественно большим, а при наличии большего количества равных ключей, чем помещается на одной странице, алгоритм просто перестает работать. Следовательно, при использовании этого кода необходимо добавить проверки, предотвращающие возникновение таких условий (см. упражнение 16.35).

С точки зрения производительности наибольший интерес представляют количество используемых страниц (как и в случае B-деревьев) и размер каталога. Для этого алгоритма рандомизация обеспечивается хеш-функциями, поэтому характеристики производительности для среднего случая верны и для любой последовательности N вставок различных ключей.

Программа 16.8. Вставка в каталог расширяемого хеширования

Этот с виду простой код лежит в основе процесса расширяемого хеширования. Вначале имеется ссылка t на узел, содержащий элементы с совпадающими первыми к разрядами, которую нужно вставить в каталог. В простейшем случае, если d и k равны, достаточно просто записать t в d[x], где x — значение первых d разрядов t->b[0] (и всех остальных элементов на странице). Если k больше d, размер каталога нужно удваивать, пока d и k не станут равны. Если k меньше d, необходимо записать более одной ссылки — в первом цикле for вычисляется количество необходимых ссылок ( 2d-k ), а во втором выполняется собственно установка.

  void insertDIR(link t, int k)
    { int i, m, x = bits(t->b[0].key(), 0, k);
      while (d < k)
        { link *old = dir;
          d += 1; D += D;
          dir = new link[D];
          for (i = 0; i < D; i++) dir[i] = old[i/2];
          if (d < k) dir[bits(x, 0, d)A1] = new node;
        }
      for (m = 1; k < d; k++) m *= 2;
      for (i = 0; i < m; i++) dir[x*m+i] = t;
    }
      

Обратите внимание, что размер каталога возрастает быстрее чем линейно относительно N, особенно при малых M. Однако для значений N и M, встречающихся на практике, значение N1/M достаточно близко к 1, поэтому реально можно ожидать, что каталог будет иметь около 4 N/M записей.

Мы считаем, что каталог — это массив ссылок. Его можно хранить в памяти или, если он слишком велик, в памяти можно хранить корневой узел, указывающий местонахождение страниц каталога, используя такую же схему индексирования. Или же можно добавить еще один уровень, индексируя первый уровень, скажем, по первым 10 разрядам, а второй — по остальным разрядам (см. упражнение 16.36).

Как и в случае B-деревьев, реализация всех остальных операций таблицы символов оставлена в качестве упражнений (см. упражнения 16.38—16.41). И так же, как и в случае B-деревьев, правильная реализация операции удалить представляет собой сложную задачу, но можно разрешить наличие мало заполненных страниц — эта легко реализуемая альтернатива может оказаться эффективной во многих возникающих на практике ситуациях.

Упражнения

16.27. Сколько страниц будут пусыми, если на рис 16.10 использовать каталог, размер которого равен 32?

16.28. Нарисуйте рисунки наподобие рис 16.13, иллюстрирующие процесс вставки ключей 562, 221, 240, 771, 274, 233, 401, 273 и 201 в указанном порядке в первоначально пустое дерево, при M= 5.

16.29. Нарисуйте рисунки наподобие рис 16.13, иллюстрирующие процесс вставки ключей 562, 221, 240, 771, 274, 233, 401, 273 и 201 в указанном порядке в первоначально пустое дерево, при M= 3.

16.30. Допустим, что имеется массив упорядоченных элементов. Опишите, как можно было бы определить размер каталога расширяемой хеш-таблицы, соответствующей этому набору элементов.

16.31. Напишите программу, которая строит расширяемую хеш-таблицу из массива упорядоченных элементов, выполняя два прохода по элементам: один для определения размера каталога (см. упражнение 16.30) и второй — для распределения элементов по страницам и заполнения каталога.

16.32. Приведите набор ключей, для которого соответствующая расширяемая хеш-таблица имеет каталог размером 16, если в одной странице помещается 8 ссылок.

16.33. Создайте рисунок наподобие рис 16.8 для расширяемого хеширования.

16.34. Напишите программу для вычисления среднего количества внешних страниц и среднего размера каталога для расширяемой хеш-таблицы, построенной N случайными вставками в первоначально пустое дерево, при емкости страницы M. Вычислите процент неиспользуемой памяти при M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.35. Добавьте в программу 16.7 проверки, необходимые для предотвращения неправильной работы при вставке в таблицу слишком большого количества одинаковых ключей или ключей, у которых совпадает слишком много ведущих разрядов.

16.36. Измените реализацию расширяемого хеширования, приведенную в программах 16.5—16.7, так, чтобы в ней использовался двухуровневый каталог, в каждом узле которого содержится не более M указателей. Обратите особое внимание на выбор действий, когда каталог впервые разрастается с одного до двух уровней.

16.37. Измените реализацию расширяемого хеширования, приведенную в программах 16.5—16.7, чтобы в структуре данных в одной странице могло находиться M элементов.

16.38. Реализуйте операцию сортировать для расширяемой хеш-таблицы.

16.39. Реализуйте операцию выбрать для расширяемой хеш-таблицы.

16.40. Реализуйте операцию удалить для расширяемой хеш-таблицы.

16.41. Реализуйте операцию удалить для расширяемой хеш-таблицы, используя метод, описанный в упражнении 16.25.

16.42. Разработайте версию расширяемого хеширования, которая при разбиении каталога разбивает и страницы, чтобы каждая ссылка каталога указывала на уникальную страницу. Экспериментально сравните производительность этой реализации с производительностью стандартной реализации.

16.43. Экспериментально определите количество случайных чисел, которые будут сгенерированы, прежде чем встретятся более M чисел с одинаковыми d начальными разрядами, при M= 10, 100 и 1000 и при $$$1 \leq d\leq 20$$$.

16.44. Измените алгоритм хеширования с цепочками переполнения (программа 14.3), чтобы в нем использовалась хеш-таблица размером 2M и элементы хранились в страницах размером 2M. Другими словами, когда страница заполняется, к ней привязывается новая пустая страница, чтобы каждая запись хеш-таблицы указывала на связный список страниц. Экспериментально определите среднее количество проб, необходимых для выполнения поиска после построения таблицы из N элементов со случайными ключами, при M= 10, 100 и 1000 и N= 103, 104, 105 и 106 .

16.45. Измените алгоритм двойного хеширования (программа 14.6), чтобы в нем использовались страницы размером 2M, а обращения к полным страницам интерпретировались как " коллизии " . Экспериментально определите среднее количество проб, необходимое для выполнения поиска после построения таблицы из N элементов со случайными ключами, при M= 10, 100 и 1000 и N= 103, 104, 105 и 106 , при начальном размере таблицы равном 3N/2M.

Перспективы

Наиболее важное применение рассмотренных в этой главе методов — это построение индексов для очень больших баз данных, хранимых во внешней памяти, например, в дисковых файлах. Хотя рассмотренные фундаментальные алгоритмы обладают большими возможностями, разработка реализации файловой системы, основанной на использовании B-деревьев или расширяемого хеширования, представляет собой сложную задачу. Во-первых, приведенные в этом разделе С++-программы нельзя использовать непосредственно — они должны быть модифицированы для считывания и обращения к дисковым файлам. Во-вторых, необходимо быть уверенным, что параметры алгоритма (например, размеры страницы и каталога) подобраны с учетом характеристик конкретного используемого аппаратного обеспечения. В-третьих, следует уделить внимание надежности, а также выявлению и исправлению ошибок. Например, необходимо иметь возможность убедиться в целостности структуры данных и принять решение о том, как исправить любую из множества возможных ошибок. Подобные системные факторы являются критичными и выходят за рамки этой книги.

С другой стороны, при наличии среды программирования, которая поддерживает виртуальную память, рассмотренные реализации на языке C++ можно непосредственно использовать в ситуации, когда необходимо выполнять очень большое количество операций в очень большой таблице символов. В первом приближении можно сказать, что при каждом обращении к странице такая система будет помещать эту страницу в кэш, в котором ссылки на данные этой страницы обрабатываются более эффективно. При обращении к странице, отсутствующей в кэше, система должна считать страницу из внешней памяти, поэтому случаи отсутствия страницы в кэше можно считать приблизительным эквивалентом используемой нами меры затрат на пробу.

При использовании B-деревьев каждый поиск или вставка обращается к корню, поэтому корень будет присутствовать в кэше всегда. В противном случае, если M достаточно велико, типичные случаи поиска или вставки максимум два раза обращаются к страницам вне кэша. При достаточно большом объеме кэш-памяти велика вероятность того, что первая страница, к которой происходит обращение при поиске (дочерняя страница корня), уже присутствует в кэше, поэтому средние затраты на один поиск, скорее всего, будут значительно меньше двух проб.

При использовании расширяемого хеширования маловероятно, что весь каталог будет храниться в кэше, поэтому можно ожидать, что обращения и к каталогу, и к странице не будут попадать в кэш (худший случай). То есть для выполнения поиска в очень большой таблице требуются две пробы: одна для обращения к соответствующей части каталога, а другая для обращения к соответствующей странице.

Эти алгоритмы завершают наше знакомство с поиском, поскольку для их эффективного использования требуется понимание базовых свойств бинарного поиска, деревьев бинарного поиска, сбалансированных деревьев, хеширования и trie-деревьев — базовых алгоритмов поиска, которые были изучены в лекциях 12—15. Все вместе эти алгоритмы предоставляют решения для задачи реализации таблицы символов во множестве ситуаций и представляют собой прекрасный пример возможностей технологии алгоритмов.

Упражнения

16.46. Разработайте реализацию таблицы символов с использованием B-деревьев, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить и объединить для АТД таблицы символов с поддержкой клиентских дескрипторов (см. упражнения 12.6 и 12.7).

16.47. Разработайте реализацию таблицы символов с использованием расширяемого хеширования, которая включает в себя деструктор, конструктор копирования и перегруженную операцию присваивания и поддерживает операции создать, подсчитать, найти, вставить, удалить и объединить для АТД таблицы символов с поддержкой клиентских дескрипторов (см. упражнения 12.6 и 12.7).

16.48. Измените реализацию B-дерева, приведенную в разделе 16.3 (программы 16.1—16.3), чтобы в ней для обращений к страницам использовался абстрактный тип данных.

16.49. Измените реализацию расширяемого хеширования, приведенную в разделе 16.4 (программы 16.5—16.8), чтобы в ней для обращений к страницам использовался абстрактный тип данных.

16.50. Оцените среднее количество проб, затрачиваемое на каждый поиск в B-дереве, при выполнении S случайных поисков в типичной кэш-системе, хранящей в памяти T страниц, к которым выполнялись последние обращения (т.е. они не увеличивают значение счетчика проб). Считайте, что S значительно больше T.

16.51. Оцените среднее количество проб на каждый поиск в расширяемой хеш-таблице для модели кэш-памяти, описанной в упражнении 16.50.

16.52. Если используемая вами система поддерживает виртуальную память, разработайте и проведите эксперименты для сравнения производительности B-деревьев с производительностью бинарного поиска при выполнении случайных поисков в очень большой таблице символов.

16.53. Реализуйте АТД очереди с приоритетами, поддерживающий операцию создать для очень большого количества элементов, вслед за которой выполняется очень много операций вставить и удалить наибольший (см.

16.54. Разработайте АТД внешней таблицы символов, основанной на представлении B-деревьев в виде слоеного списка (см. упражнение 13.80).

16.55. Если используемая вами система поддерживает виртуальную память, определите экспериментально значение M, которое обеспечивает наименьшее время выполнения для реализации B-дерева, поддерживающей случайные операции вставить в очень большой таблице символов. (Прежде чем выполнять подобные эксперименты, которые могут потребовать больших затрат, стоит ознакомиться с основными характеристиками системы.)

16.56. Измените реализацию B-дерева, приведенную в разделе 16.3 (программы 16.1—16.3), чтобы она работала в среде, в которой таблица размещается на внешнем запоминающем устройстве. Если применяемая файловая система допускает произвольный доступ к файлам, поместите всю таблицу в один (очень большой) файл, и в структуре данных вместо ссылок используйте смещения внутри файла. Если система допускает непосредственное обращение к страницам на внешних устройствах, то в структуре данных вместо ссылок используйте адреса страниц. Если система допускает оба вида доступа, выберите подход, который, по вашему мнению, наиболее подходит для реализации очень большой таблицы символов.

16.57. Измените реализацию таблицы расширяемого хеширования, приведенную в разделе 16.4 (программы 16.5—16.8), чтобы она работала в среде, в которой таблица размещается на внешнем запоминающем устройстве. Объясните причины выбранного вами способа распределения каталога и страниц по файлам (см. упражнение 16.56).

Ссылки для части IV

Основные источники для этого раздела — книги Кнута (Knuth); Баеса-Ятеса (Baeza-Yates) и Гонне (Gonnet); Мельхорна (Mehlhorn); и Кормена (Cormen), Ляйзерзона (Leiserson) и Райвеста (Rivest). В этих книгах подробно рассматриваются многие из приведенных в этой части алгоритмов, вместе с математическим анализом и предложениями по практическому применению. Классические методы подробно изложены в книге Кнута; более поздние методы описаны в остальных книгах, в них же приводятся ссылки на другую литературу. В этих четырех источниках, а также в книге Седжвика (Sedgewick) и Флажоле (Flajolet) описан практически весь материал, который упоминался как "выходящий за рамки этой книги".

Материал, приведенный в , взят из статьи Роура (Roura) и Мартинеса (Martinez) за 1996 г., статьи Слитора (Sleator) и Тарьяна (Tarjan) за 1985 г. и статьи Гиба (Guibas) и Седжвика за 1978 г. Как видно из дат публикации этих статей, исследование сбалансированных деревьев продолжается. Перечисленные источники содержат подробные доказательства свойств RB-деревьев и аналогичных им структур, а также ссылки на более современные работы.

Трактовка trie-деревьев, приведенная в , является классической (хотя в литературе редко можно встретить реализации на языке C++). Материал по TST-деревьям взят из статьи Бентли (Bentley) и Седжвика за 1997 г.

B-деревья впервые рассматриваются в статье Байера (Bayer) и Мак-Крейта (McCreight) за 1972 г., а алгоритм расширяемого хеширования, представленный в главе 16, взят из статьи Фагина (Fagin), Нивергельта (Nievergelt), Пиппенгера (Pippenger) и Стронга (Strong), опубликованной в 1979 г. Аналитические результаты по расширяемому хешированию были получены Флажоле в 1983 г. С этими статьями следует обязательно ознакомиться всем, кто желает получить более подробную информацию по методам внешнего поиска. Практическое применение этих методов обусловлено распространенностью систем управления базами данных. С введением в эту область можно ознакомиться, например, в книге Дейта (Date).

1. R. Baeza-Yates and G. H. Gonnet, НаМЬоок of Algorithms and Data Structures, second edition, Addison-Wesley, Reading, MA, 1984.

2. J. L. Bentley and R. Sedgewick, "Sorting and searching strings," Eighth Symposium on Discrete Algorithms, New Orleans, January, 1997.

3. R. Bayer and E. M. McCreight, "Organization and maintenance of large ordered indexes," Acta Informatica 1, 1972.

4. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн, Алгоритмы: построение и анализ, 2-е издание, ИД "Вильямс", 2009 г.

5. К. Дж. Дейт, Введение в системы баз данных, 7-е издание, ИД "Вильямс", 2001 г.

6. R. Fagin, J. Nievergelt, N. Pippenger and H. R. Strong, "Extendible hashing—a fast access method for dynamic files," ACM Transactions on Database Systems 4, 1979. 7. P Flajolet, "On the performance analysis of extendible hashing and trie search," Acta Informatica 20, 1983.

8. L. Guibas and R. Sedgewick, "A dichromatic framework for balanced trees," in 19th Annual Symposium on Foundations of Computer Science, IEEE, 1978. Также в A Decade of Progress 1970-1980, Xerox PARC, Palo Alto, CA.

9. Д.Э. Кнут, Искусство программирования, том 3. Сортировка и поиск, 2-е издание, ИД "Вильямс", 2008 г.

10. K. Mehlhorn, Data Structures and Algorithms 1: Sorting and Searching, Spiinger-Vferlag, Berlin, 1984.

11. S. Roura and C. Martinez, "Randomization of search trees by subtree size," Fourth European Symposium on Algorithms, Barcelona, September, 1996.

12. R. Sedgewick and P Flajolet, An Introduction to the Analysis of Algorithms, Addison-Wesley, Reading, MA, 1996.

13. D. Sleator and R. E. Tarjan, "Self-adjusting binary search trees," Journal of the ACM 32, 1985.