Расчет глубины индекса

Индексы в большинстве случаев (по крайней мере в Firebird и InterBase) представляют собой страничные B*-деревья. Скорость поиска ключа в дереве напрямую зависит от количества страниц, просматривая которые сервер доберется до указателя на запись.

Например, при помощи GSTAT вы получили статистику по БД, и один из индексов выглядит следующим образом (размер страницы для этой БД – 8192 байт):

Index RDB$PRIMARY33 (0)
  Depth: 3, leaf buckets: 469, nodes: 88926
  Average data length: 36.00, total dup: 0, max dup: 0
  Fill distribution:
      0 - 19% = 0
     20 - 39% = 0
     40 - 59% = 0
     60 - 79% = 1
     80 - 99% = 468

Depth – текущая глубина индекса
Leaf buckets – листовых страниц дерева. Т. е. кол-во страниц, на которых находятся ссылки на записи.

Получить среднее количество ключей на странице можно поделив число nodes на leaf buckets. Для примера это 88926 / 469 = 190. Т. е. на странице размещается 190 ключей. Средний размер ключа = PAGE_SIZE / keys on page. Т. е. 8192 / 190 = 43. Вообще, как утверждает Ann Harrison, среднюю длину ключа можно получить, прибавив к Average data length число 6. Действительно, в примере 36 + 6 = 42, что почти равно полученным нами 43. Однако неуникальные индексы из-за сильной упаковки ключа могут в статистике показывать Average data length равным нулю.

Подсчет количества страниц предыдущего уровня (страницы указателей, которые содержат ссылки на страницы leaf buckets) – число leaf buckets – это фактически число ключей предыдущего уровня. У нас оно равно 469. Нужно умножить это число на среднюю длину ключа, и поделить на размер страницы.
(469 * 43) / 8192 = 3 (2.46 округляется вверх до ближайшего целого. Мы ведь считаем число страниц, а даже 0.1 страницы – это уже занятая страница).

Самый первый уровень дерева индекса всегда содержит одну страницу.

Предельным количеством ключей в первой странице является 190 (8192 / 43). Таким образом, глубина индекса, равная 3, будет сохраняться до тех пор, пока во втором уровне 190 страниц. Соответственно, количество страниц третьего уровня равно (190 * 8192) / 43 = 36198. В выражении количества записей это равно
(36198 * 8192) / 43 = 6 миллионов, 896 тысяч 140 записей.

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

Первая страница = 190 ключей * 0.7 = 133 ключа (страницы второго уровня)
133 страницы второго уровня * 8192 / 43 * 0.7 =  17737 страниц третьего уровня (leaf buckets)
кол-во записей = 17737 * 8192 / 43 * 0.7 = 2 миллиона 365 тысяч 374 записи.

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