Красно-чёрное дерево (Red-black tree, RB-Tree) — самобалансирующееся двоичное дерево поиска, гарантирующих логарифмический рост высоты от числа узлов.
Дополнительные требования к двоичному дереву:
1. Узел либо красный, либо чёрный
2. Корень — чёрный
3. Все листья (NIL) — чёрные (листья не содержат данных)
4. Оба потомка каждого красного узла — чёрные.
5. Всякий простой путь от данного узла до любого листового узла, являющегося его потомком, содержит одинаковое число чёрных узлов.
Эти ограничения реализуют главное свойство красно-чёрных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа.
Результатом является то, что дерево примерно сбалансировано.
Реализацию красно-черного дерева на java можно посмотреть тут: RBTree.java
Но в такой реализации оно сложно для понимания и программистам бд более близка реализация через B-дерево с фактором = 4.
В таком дереве каждый узел может содержать от 1 до 3 значений и от 2 до 4 указателей на потомков.
Если страница В-дерева содержит только одно значение, данный узел чёрный и имеет двух потомков.
Если страница содержит три значения, то центральный узел является чёрным, а каждый его сосед — красным.
Однако, если страница содержит два значения, любой узел может стать чёрным в красно-чёрном дереве (и тогда второй будет красным).
Пример реализации красно-черного дерева на основе B-дерева с размером блока = 3 можно посмотреть тут: BTree.scala
Для программистов БД нужно помнить 2 отличия B-дерева от B+дерева:
* при разделение элемент переносится наверх (не остается в листе)
* листы не связаны друг с другом ссылками
Красно-чёрные деревья являются одними из наиболее активно используемых на практике самобалансирующихся деревьев поиска.
В частности, контейнеры set и map в большинстве реализаций библиотеки STL языка C++, класс TreeMap языка Java, ассоциативный массив, когда реализация через списки дает слишком много коллизий
( подробное описание хэш массива тут: 3ий вариант реализации Oracle HashMap )
Популярность красно-чёрных деревьев связана с тем, что на них часто достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности при удалении.
Следующий аспект бд - хэширование данных
Раньше я уже описывал hash join со стороны разработчика бд: Основы стоимостной оптимизации join, сегодня копнем немного глубже, с кодом hash join на java.
Хэширование - преобразование массива входных данных произвольной длины в выходную битовую строку фиксированной длины, выполняемое определённым алгоритмом.
Преимуществом массива фиксированной длины является константное время доступа к его элементам из-за размещения ограниченного набора в процессорном кэше.
Самая большая проблема - это выбор хэширующей функции, которая давала бы минимум коллизий (одинаковых значений хэш функции для разных ключей массива).
Идеальная хэширующая функция не должна давать коллизий, но в реальности такую функцию сложно получить.
В моем случае алгоритмом хэширование я выбрал остаток от деления. Число в знаменателе даст нам такое же число элементов в хэш массиве.
Для разрешения проблемы коллизий используется 2 подхода, оба из них в зависимости от числа коллизий для доступа к нужному элементу дают от 1 до N обращений:
1. Открытая адресация
Коллизии размещаются в томже хэш массиве, но смещаются вправо, пока не найдется свободное место.
Пример:
Массив из элементов: 1, 11, 2, 3
Хэширующая функция: остаток от деления на 10
Результирующий хэш массив:
[1] = 1 (остаток от деления 1 на 10 = 1, т.к. ключ 1 был пустой, то он и занимается)
[2] = 11 (остаток от деления 11 на 10 = 1, это коллизия для предыдущего элемента. Т.к. ключ 1 занят, то берется следующий пустой справа = 2)
[3] = 2 (остаток от деления = 2, т.к. элемент занят, то берется следующий = 3)
[4] = 3 (и т.д.)
2. Метод цепочек
Хэш таблица содержит список коллизий. Число элементов хэш таблицы фиксировано = числу различных вариантов хэширующей функции.
Пример на том же массиве и той же хэширующей функции:
[1] = 1 -> 11
[2] = 2
[3] = 3
[4] = 4
3. Метод красно-черного дерева
В случае большого числа коллизий, когда все элементы попадают в одну хэш секцию, для хранения данных секции целесообразно использовать красно-черное дерево, замен списка во 2 методе. В этом случае поиск элемента будет осуществляться за логарифмическое время, вместо линейного в списке.
Плюсы и минусы подходов:
Сравниваемое свойство
Цепочки
Открытая адресация
Разрешение коллизий
Используются дополнительные списки
Хранится в самом хэш массиве
Использование памяти
Дополнительная память для указателей в списке.
В случае неудачной хэш функции, если все элементы легли в один элемент массива (хэш секцию), то размер памяти будет почти в 2 раза больше, т.к. необходимая память под указатели будет равна памяти под ключи.
Нет доп. расходов
Зависимость производительности от заполненности таблицы
Прямо пропорционально значению = число элементов / кол-во хэш секции таблицы
число элементов / ( кол-во хэш секции таблицы - число элементов )
Возможность записи числа элементов больше размера хэш таблицы
Да, за счет записи коллизий в список
Нет, т.к. колллизии храняться в томже массиве
Простота удаления
Да, удаляется элемент из списка
Нет, пустое место нужно помечать удаленным, а не очищать физически. Т.к. при вставке ищутся пусты места справа, что может сломать последовательность
Использование кэша процессора
Нет (переходы по ссылке)
Да (Все данные рядом)
Детали реализации Oracle:
Хэширование цепочками наиболее понятное, но оно же дает худшую производительность, т.к. не использует кэш процессора из-за постоянных переходов по ссылке.
По этому все нагруженные реализации используют Hash таблицы с открытой адресацией, где все данные лежат рядом и используют кэш сопроцессора.
Слева графически представлен механизм поиска в хэш таблице Oracle.
Изменения в реализации хэш таблиц Oracle:
* Хэш таблица над таблицей бд может быть сколь угодно большой и она может не поместиться в памяти
* битовая карта над данными в хэш таблице, если соответствующий бит таблицы установлен, то элемент есть в хэш таблице, иначе строку можно даже не искать.
Когда Oracle выбирает соединение хэшированием:
В основе выбора способ лежит стоимостная оценка: Стоимость соединения вложенными циклами (NL) = стоимость получения T1 + кардинальность Т1 * Стоимость одного обращения к Т2 Стоимость соединения хэшированием (hash) = стоимость получения Т1 + стоимость получения Т2 + стоимость хэширования и сравнения.
Исходя из этих формул можно сделать вывод, что hash соединение выгодней, когда :
* Нужно считать большой объем данных для соединения или на правой таблице таблице нет индекса.
Многоблочное считывание при hash join выгодней, чем последовательное одноблочное сканирование индекса правой таблицы.
* Параллельное выполнение запросов - хэширование и поиск в хэш таблице хорошо распараллеливается, поиск по связанному списку индекса практически не параллелится.
Когда hash join не может быть использован:
* Поиск по диапазону (или любой операции отличной от = ) не применим для хэш таблицы, результат функции дает непоследовательные данные, которые не просканировать последовательно.
Рассмотрим подробней вариант, однопроходного поиска в хэш таблице, т.е. когда объема памяти достаточно, чтобы целиком разместить хэш секцию.
Для простоты будет использоваться Hash таблица цепочками.
Основная мысль, которую надо понять при работе с параллельными запроса: "At most one data distribution can be active at the same time" - только одно распределение данных ( PQ Distrib / PX SEND ) может работать одновременно.
Это является причиной появления операций HASH JOIN BUFFERED или BUFFER SORT в параллельных планах, именно они сбивают с мысли человека привыкшего к последовательным не параллельным запросам.
Может сложиться ошибочное мнение о том что при выполнении HASH JOIN закончился hash area size и oracle свопит промежуточные данные на диск/память или делается какаято сортировка, чтобы потом выполнить merge join.
В реальности, как я уже сказал ранее, на параллельные запросы накладывается дополнительное условие: только одно распределение данных ( PQ Distrib / PX SEND ) может работать в один момент.
Это вынуждает складировать промежуточные данные других потоков до конца выполнения распределения, что является причиной появления буферных операций HASH JOIN BUFFERED и BUFFER SORT.
Рассмотрим на примере:
Создадим 2 таблицы:
create table t2
compress
as
select
rownum as id
, mod(rownum, 1000) + 1 as fk
, rpad('x', 100) as filler
from
dual
connect by
level <= 1000000
;
exec dbms_stats.gather_table_stats(null, 't2')
-- Create a copy of T2
create table t4
compress as
select * from t2;
insert /*+ append */ into t4
select
1000000 + rownum as id
, 1000 + mod(rownum, 1000) + 1 as fk
, rpad('x', 100) as filler
from
dual
connect by
level <= 1000000
;
commit;
exec dbms_stats.gather_table_stats(null, 't4')
alter table t2 parallel 2;
alter table t4 parallel 2;
Oracle может выполнить hash join 3 разными способами.
Хинты заданы, чтобы точно гарантировать последовательность работы.
Через хинт pq_distribute(b, hash, hash) мы задаем способ обмена данными между потоками - в данном случае hash.
Используя мониторинг становится ясна последовательность выполнения (Timeline):
1. PX SEND HASH :TQ10000 - левая таблица целиком хэшируется и отправляется в :TQ10002
2. PX SEND HASH :TQ10001 - правая таблица также целиком хэшируется и отправляется в :TQ10000.
Так же до этапа HASH JOIN происходит откидывание несоответствующих хэшей правой таблицы (Randolf подтверждает это трассировкой и рассчетами на основании количества строк в правой hash таблице)
Дополнительная затраченная память отображается в столбце Memory.
3. PX SEND QC (RANDOM) :TQ10002 - происходит соединение таблиц используя хэши левой и правой таблицы + параллельная отправка промежуточных данных на следующий этап.
Такая последовательность действий обеспечивает нам 1 рабочий PX SEND одновременно.
Способ 2: HASH JOIN альтернативный план, когда хэш правой таблицы передается постепенно и не буферизуется.
Чтобы получить его, достаточно добавить агрегирующую функцию (count/min/max) - что заблокирут передачу промежуточных данных на уровень выше.
1. PX SEND HASH :TQ10000 - левая таблица целиком хэшируется и отправляется в :TQ10002
2. PX SEND HASH :TQ10001 - правая таблица построчно хэшируется и отправляется в :TQ10000.
Эта операция не требует дополнительных затрат памяти.
3. HASH JOIN - происходит построчное соединение таблиц используя хэши левой и правой таблицы.
4. PX SEND QC (RANDOM) :TQ10002 - отправка результата дальше, выполняется после полного выполнения этапа 2, т.е. после полного выполнения HASH JOIN этапа 3.
Способ 3: BUFFER SORT альтернативный план, в целом похожий на HASH JOIN BUFFERED
Меняем метод рассылки данных на BROADCAST - копирование данных во все потоки.
В этом случае хэши правой таблицы не создаются, вместо этого данные помещаются в BUFFER SORT и используются при выполнении HASH JOIN
1. PX SEND BROADCAST :TQ10000 - правая таблица целиком пересылается в BUFFER SORT
Надо заметить, что BUFFER SORT в этом случае ничего не сортирует, а только буферизирует данны.
Объем потребленной памяти = размер правой таблицы * параллелизм (из-за broadcast во все потоки).
2. HASH JOIN - происходит полное соединение таблиц.
4. PX SEND QC (RANDOM) :TQ10001 - отправка результата дальше по мере готовности.
Объем памяти в BUFFER SORT не растет во время выполнения, что подтверждает предположение - правая таблица целиком помещается в буфер сразу на первом этапе.
Вывод: обычный hash join лучше, когда памяти мало, т.к. нет операций с temp/памятью.
Если памяти достаточно, то hash join buffered предпочтительней, т.к. oracle может сразу перейти к следующему этапу запроса и получить большую степерь параллелизма.
Эти ограничения реализуют главное свойство красно-чёрных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа. 
В таком дереве каждый узел может содержать от 1 до 3 значений и от 2 до 4 указателей на потомков. 
Коллизии размещаются в томже хэш массиве, но смещаются вправо, пока не найдется свободное место.
Хэш таблица содержит список коллизий. Число элементов хэш таблицы фиксировано = числу различных вариантов хэширующей функции.
Слева графически представлен механизм поиска в хэш таблице Oracle.
