Индексы в большинстве случаев (по крайней мере в IB) представляют собой страничные 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 миллиона записей в таблице. Реально это
зависит от частоты обновления индекса, т.е. от фрагментации страниц индекса.
Если первичный ключ не модифицируется, то пороговое количество записей будет
больше. Если модифицируется - то меньше.
примечание: можно посчитать и максимальное количество ключей, при котором
глубина индекса будет оставаться равной четырем. Это
2365374 * 8192 / 43 * 0.7 = 315 миллионов 441 тысяч 876 записей.
таким образом, производительность выборок с использованием индекса будет одинаковой
при кол-ве ключей от 2.3 миллиона до 315 миллионов.
Необходимо заметить, что все приведенные вычисления не имеют никакого отношения к размеру таблицы, т.е. предельному количеству записей для таблицы.
www.ibase.ru, (c) KDV