Расчет глубины индекса
Индексы в большинстве случаев (по крайней мере в 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 миллиона записей в таблице. Реально это зависит от частоты обновления индекса, т. е. от фрагментации страниц индекса. Если первичный ключ не модифицируется, то пороговое количество записей будет больше. Если модифицируется то меньше.
Примечание. Можно посчитать и максимальное количество ключей, при котором глубина индекса будет оставаться равной четырем. Это
2365374 * 8192 / 43 * 0.7 = 315 миллионов 441 тысяч 876 записей. Таким образом, производительность выборок с использованием индекса будет одинаковой при кол-ве ключей от 2.3 миллиона до 315 миллионов.
Необходимо заметить, что все приведенные вычисления не имеют никакого отношения к размеру таблицы, т. е. предельному количеству записей для таблицы.
Copyright iBase.ru © 2002-2022
Источник
Индексируемое бинарное дерево
Попалась мне задача следующего вида. Необходимо реализовать контейнер хранения данных обеспечивающий следующий функционал:
- вставить новый элемент
- удалить элемент по порядковому номеру
- получить элемент по порядковому номеру
- данные хранятся в сортированном виде
Данные постоянно добавляются и удаляются, структура должна обеспечивать быструю скорость работы. Сначала пытался реализовать такую вещь используя стандартные контейнеры из std. Этот путь не увенчался успехом и пришло понимание, что нужно реализовывать что-то самому. Единственное что пришло на ум, это использовать бинарное дерево поиска. Поскольку оно отвечает требованию быстрой вставки, удалению и хранению данных в сортированном виде. Осталось только придумать как проиндексировать все элементы и пересчитывать индексы когда дерево меняется.
В статье будет больше картинок и теории чем кода. Код можно будет посмотреть по ссылке внизу.
Вес
Для этого дерево подверглось небольшой модифицикации, добавилась дополнительная информация о весе узла. Вес узла это кол-во потомков данного узла + 1 (вес единичного элемента).
Функция получения веса узла:
uint64_t bntree::get_child_weight(node_t *node) < if (node) < return node->weight; > return 0; >У листа соответственно вес равен 0.
Далее перейдем к наглядному представлению примера такого дерева. Черным цветом в нем будет показан ключ узла (значение показано не будет, т.к. в этом нет надобности), красным — вес узла, зеленым — индекс узла.
Когда дерево у нас пусто, то его вес равен 0. Добавим в него корневой элемент:
Вес дерева становится 1, вес корневого элемента 1. Вес корневого элемента является весом дерева.
Добавим еще несколько элементов:
Каждый раз когда идет добавление нового элемента, мы спускаемся по узлам в низ и увеличиваем счетчик веса каждого пройденного узла. При создании нового узла ему выставляется вес 1. Если узел с таким ключом уже существует, то перезапишем значение и пойдем назад до корня вверх отменяя изменения весов у всех узлов которые мы прошли.
Если идет удаление узла, то мы спускается вниз и декрементируем веса пройденных узлов.
Индексы
Теперь перейдем к тому как проиндексировать узлы. Узлы явно не хранят свой индекс, он вычисляется на основе веса узлов. Если бы они хранили свой индекс, то требовалось бы O(n) времени, что бы обновить индексы всех узлов после каждого изменения дерева.
Перейдем к наглядному представлению. Наше дерево пусто, добавим в него 1-ый узел:
Первый узел имеет индекс 0, а теперь возможны 2-а случая. В первом индекс корневого элемента изменится, во втором не изменится.
У корня левое поддерево весит 1.
Индекс корня не изменился, поскольку вес его левого поддерева остался 0.
Как считается индекс узла, это вес его левого поддерева + число переданное от родителя. Что это за число?, Это счетчик индексов, изначально он равен 0, т.к. у корня нет родителя. Дальше все зависит от того куда мы спускаемся к левому ребенку или правому. Если к левому, то к счетчику ни чего не прибавляется. Если к правому то прибавляем индекс текущего узла.
К примеру как вычисляется индекс элемента с ключом 8 (правый ребенок корня). Это «Индекс корня» + «вес левого поддерева узла с ключом 8» + «1» == 3 + 2 + 1 == 6
Индексом элемента с ключом 6 будет «Индекс корня» + 1 == 3 + 1 == 4
Соответственно что бы получить, удалить элемент по индексу требуется время O(log n), поскольку что бы получить нужный элемент мы должны сначала его найти (спуститься от корня до этого элемента).
Глубина
На основе веса так же можно вычислить и глубину дерева. Необходимую для балансировки.
Для этого вес текущего узла надо округлить до первого числа в степени 2 которое больше или ровно данному весу и взять от него двоичный логарифм. Таким образом мы получим глубину дерева, при условии что оно сбалансировано. Дерево балансируется после вставки нового элемента. Теорию про то как балансировать деревья приводить не буду. В исходных кодах представлена функция балансировки.
Код приведения веса к глубине.
/* * Возвращает первое число в степени 2, которое больше или ровно x */ uint64_t bntree::cpl2(uint64_t x) < x = x - 1; x = x | (x >> 1); x = x | (x >> 2); x = x | (x >> 4); x = x | (x >> 8); x = x | (x >> 16); x = x | (x >> 32); return x + 1; > /* * Двоичный логарифм от числа */ long bntree::ilog2(long d) < int result; std::frexp(d, &result); return result - 1; >/* * Вес к глубине */ uint64_t bntree::weight_to_depth(node_t *p) < if (p == NULL) < return 0; >if (p->weight == 1) < return 1; >else if (p->weight == 2) < return 2; >return this->ilog2(this->cpl2(p->weight)); >Итоги
- вставка нового элемента происходит за O(log n)
- удаление элемента по порядковому номеру происходит за O(log n)
- получение элемента по порядковому номеру происходит за O(log n)
Скоростью O(log n) платим за то, что все данные хранятся в сортированном виде.
Где может пригодиться такая структура — не знаю. Просто задачка, что бы еще раз разобраться как работают деревья. Спасибо за внимание.
Ссылки
В проекте содержатся тестовые данные для проверки скорости работы. Дерево заполняется 1000000 элементов. И происходит последовательное удаление, вставка и получение элементов 1000000 раз. То есть 3000000 операций. Результат оказался вполне неплохим ~ 8 секунд.
Источник
Многоуровневые индексы
При возрастании размера индексного файла и расширении его содержимого на большое количество страниц время поиска нужного индекса также значительно возрастает. Обратившись к многоуровневому индексу, можно попробовать решить эту проблему путем сокращения диапазона поиска. Данная операция выполняется над индексом аналогично тому, как это делается в случае файлов другого типа, т.е. посредством расщепления индекса на несколько субиндексов меньшего размера и создания индекса для этих субиндексов. На каждой странице файла данных могут храниться две записи. Кроме того, в качестве иллюстрации здесь показано, что на каждой странице индекса также хранятся две индексные записи, но на практике на каждой такой странице может храниться намного больше индексных записей. Каждая индексная запись содержит значение ключа доступа и адрес страницы. Хранимое значение ключа доступа является наибольшим на адресуемой странице.
Усовершенствованные сбалансированные древовидные индексы
Дерево — это структура данных, используемая во многих СУБД для хранения данных или индексов. Дерево состоит из иерархии узлов (node), в которой каждый узел, за исключением корня (root), имеет родительский (parent) узел, а также один, несколько или ни одного дочернего (child) узла. Корень не имеет родительского узла. Узел, который не имеет дочерних узлов, называется листом (leaf).
Глубина дерева — это максимальное количество уровней между корнем и листом. Глубина дерева может быть различной для разных путей доступа к листам.
Сбалансированное дерево, В-дерево, В-Тгее — это дерево, у которого глубина дерева одинакова для всех листов.
Степень (degree), порядок (order) дерева — это максимально допустимое количество дочерних узлов для каждого родительского узла. Большие степени обычно используются для создания более широких и менее глубоких деревьев.
Поскольку время доступа в древовидной структуре зависит от глубины, а не от ширины, обычно принято использовать более «разветвленные» и менее глубокие деревья.
Бинарное дерево, binary tree — это дерево порядка 2, в котором каждый узел имеет не больше двух дочерних узлов.
Усовершенствованные сбалансированные древовидные индексы определяются по следующим правилам.
- Если корень не является лист-узлом, то он должен иметь, по крайней мере, два дочерних узла.
- В дереве порядка n каждый узел (за исключением корня и листов) должен иметь от n/2 до n указателей и дочерних узлов. Если число n/2 не является целым, то оно округляется до ближайшего большего целого.
- В дереве порядка n количество значений ключа в листе должно находиться в пределах от (n-1)/2 до (n-1). Если число (n-1)/2 не является целым, то оно округляется до ближайшего большего целого.
- Количество значений ключа в нелистовом узле на единицу меньше количества указателей.
- Дерево всегда должно быть сбалансированным, т.е. все пути от корня к каждому листу должны иметь одинаковую глубину.
- Листы дерева связаны в порядке возрастания значений ключа.
Источник