Красно-чёрное дерево (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 )
Популярность красно-чёрных деревьев связана с тем, что на них часто достигается подходящий баланс между степенью сбалансированности и сложностью поддержки сбалансированности при удалении.
В условиях интенсивной вставки для быстрого доступа к данным обычные btree индексы не подходят.
Во многих базах (Bigtable, HBase, LevelDB, MongoDB, SQLite4, Tarantool, RocksDB, WiredTiger, Apache Cassandra, и InfluxDB ) используется LSM-дерево (Log-structured merge-tree — журнально-структурированное дерево со слиянием)
LSM дерево служит для хранения ключ-значения.
В данной статье рассмотрим двухуровневое дерево. Первый уровень целиком находится в памяти, вторая половина на диске.
Вставка идет всегда в первую часть в памяти, а поиск из всех частей. Когда размер данных в памяти превышает определенный порог, то она записывается на диск. После чего блоки на диске объединяются в один.
Рассмотрим алгоритм по частям:
1. Все записи в дереве маркируются порядковым номером glsn , при каждой вставке этот счетчик увеличивается
Структура для хранения ключа-значения и порядкового номера:
2. Структуры объядиняются в одну таблицу в памяти.
В моем алгоритме используется хэш таблица.
В реальности чаще всего используется отсортированная по ключу структура - это дает преимущества, что для поиска и слияния используется последовательное чтение, вместо рандомного.
class MemSSTable {
//из-за хэша нет поиска по диапазону
HashMap<Integer, SSItem> itms = new HashMap<Integer, SSItem>();
3. Т.к. размер памяти ограничен, то при превышении определенного порога, данные должны быть скинуты на диск.
В моей реализации - это простой вариант без фоновых заданий и асинхронных вызовов
При достижении лимита будет фриз, т.к. таблица скидывается на диск.
В реальных системах используется упреждающая запись: данные на диск скидываются асинхронно и заранее, до достижения жесткого лимита памяти.
void SaveToDisk() throws FileNotFoundException, UnsupportedEncodingException {
indx.path = "sstable_" + indx.max_lsn + ".dat";
PrintWriter writer = new PrintWriter(indx.path, "UTF-8");
Integer pad = 0;
//последовательно пишем 10 байт с длиной значения и само значение
for(Entry<Integer, SSItem> entry : itms.entrySet()) {
SSItem itm = entry.getValue();
String val = itm.get();
writer.print( val );
//регистрируем в индексе смещения в файле
indx.keys.put(itm.key, pad);
pad = pad + val.length();
}
writer.close();
LSMTree.indexes.add(indx);
} //SaveToDisk
4. Получается, что половина всех данных у нас хранится в хэше в памяти, а остальное в виде файлов на диске.
Чтобы не перебирать все файлы на диске создается дополнительная индексная структура, которая будет хранить метаинформацию о файлах в памяти:
//индекс над таблицей с даными
class SSTableIndex {
//метаданные:
//минимальный и максимальный ключи в таблице
Integer min_key;
Integer max_key;
//минимальный и максимальный порядковый lsn
Integer min_lsn;
Integer max_lsn;
//если таблица на диске, то путь до файла
String path;
//ключ - смещение ключа в файле
HashMap<Integer, Integer> keys = new HashMap<Integer, Integer>();
//добавить ключ в индекс
void add(Integer k) {
//также обновляем метаданные
max_lsn = LSMTree.glsn;
if(min_lsn == null) min_lsn = max_lsn;
if(min_key == null || k < min_key) min_key = k;
if(max_key == null || k > max_key) max_key = k;
//добавление идет в память в хэш таблицу, на первом этапе смещения в файле нет
keys.put(k, 0);
}
5. Управляющий объект всего дерева хранит ссылку на таблицу с данными в памяти и на мета-индексы данных на диске:
public class LSMTree {
static int glsn = 0;
//максимальный размер, после которого таблица должна быть скинута на диск
//для упрощения алгоритма = числу записей, а не размеру в байтах
final static int max_sstable_size = 10;
//текущая таблица в памяти, куда вставляем данные
MemSSTable MemTable;
//все индексы, даже для таблиц на диске, хранятся в памяти
static LinkedList<SSTableIndex> indexes = new LinkedList<SSTableIndex>();
6. Когда все объекты описаны, давайте посмотрим как происходит добавление нового элемента.
Добавление всегда идет в таблицу в памяти, что гарантирует быструю вставку:
public class LSMTree {
//....
//добавить запись
public void add(Integer k, String v) {
MemTable.add(k, v);
}
Подробней логика добавления в таблицу в памяти:
* Увеличиваем глобальный счетчик элементов LSMTree.glsn
* Если число элментов превысило порог, то таблица скидывается на диск и очищается
В реальности это конечно не число элементов, а объем в байтах.
* Создается новый элемент SSItem
* И доблавляется в хэш массив
Причем, если элемент до этого уже существовал, то он перезаписывается.
В реальности хранятся все записи, чтобы была возможность поддержки транзакционности.
* Кроме этого в индексе обновляются метаданные indx.add
class MemSSTable {
//.....
//добавить новый элемент
void add(Integer k, String v) {
//увеличиваем глобальный счетчик операций glsn
LSMTree.glsn++;
//если размер превышает,
if(itms.size() >= LSMTree.max_sstable_size) {
try {
//то сохраняем таблицу на диск
//в реальных движках используется упреждающая фоновая запись
//когда папять заполнена на N% (n<100), то данные скидываются на диск заранее, чтобы избежать фриза при сбросе памяти и записи на диск
SaveToDisk();
} catch (FileNotFoundException | UnsupportedEncodingException e) {
e.printStackTrace();
return;
}
//очищаем данные под новые значения
indx = new SSTableIndex();
itms = new HashMap<Integer, SSItem>();
}
//обновляем медаданные в индексе
indx.add(k);
SSItem itm = new SSItem(k, v, indx.max_lsn);
//в моей реализации, при повторе ключ перезаписывается
//т.е. транзакционность и многоверсионность тут не поддерживается
itms.put(k, itm);
} //add
Если после вставки нового элемента старые данные оказались на диске, то в метаданных индекса прописывается ссылка на точное смещение в файле:
class SSTableIndex {
//...
//если таблица на диске, то путь до файла
String path;
//ключ - смещение
HashMap<Integer, Integer> keys = new HashMap<Integer, Integer>();
7. С вставкой разобрались, теперь обратная операция - поиск элемента в дереве:
* Сперва мы проверяем наличие ключа в хэш таблице в памяти. Если элемент нашелся, то на этом все.
* Если элемента нет, то мы пробегамся по всем метаиндексам в поиске нашего ключа.
* проверяем, что ключ входит в диапазон indx.min_key - indx.max_key индекса
* И для полной точности проверяем наличие ключа в хэше ключей indx.keys.containsKey
* Если элемент нашелся, то это еще не конец, цикл продолжается, пока мы не переберем все индексы.
Т.к. ключ может добавляться несколько раз в разные промежутки времени.
* Из всех совпадений выбираем индекс с максимальным счетчиком вставки - это последнее изменение ключа
public class LSMTree {
//.....
//получить значение по ключу
String getKey(Integer key) {
//сперва смотрим в памяти
String val = MemTable.getKey(key);
if(val == null) {
SSTableIndex indx_with_max_lsn = null;
//потом таблицу по индексам, которая содержит наш ключ
//если содержится в нескольких, то берем с максимальным lsn, т.к. это последнее изменение
for (SSTableIndex indx : indexes) {
Integer max_lsn = 0;
if(key >= indx.min_key && key <= indx.max_key && max_lsn < indx.max_lsn ) {
if(indx.keys.containsKey(key)) {
max_lsn = indx.max_lsn;
indx_with_max_lsn = indx;
}
}
}
//читаем из таблицы с диска
if(indx_with_max_lsn != null) {
try {
return indx_with_max_lsn.getByPath(key);
} catch (IOException e) {
e.printStackTrace();
}
}
}
return val;
}
* Определим нужный индекс обращаемся по нему к таблице на диске:
** Открываем нужный файл
В реальности, скорей всего, файы постоянно держатся открытыми для экономии времени.
** Следуя смещенями из индекса переходим к нужной точке файла file.seek
** И считываем значение file.read
class SSTableIndex {
//...
//получить значение ключа из открытого файла
String getByPath(Integer key, RandomAccessFile file) throws IOException {
//получаем смещение в файле для ключа из индекса
Integer offset = keys.get(key);
//смещаемся в файле
file.seek(offset);
//резервируем 10 байт под переменную с длинной значения
byte[] lenb = new byte[10];
file.read(lenb, 0, 10);
Integer len = Integer.parseInt(new String(lenb, StandardCharsets.UTF_8));
file.seek(offset + 10);
//считываем значение
byte[] valb = new byte[len];
file.read(valb, 0, len);
return new String(valb, StandardCharsets.UTF_8);
} //getByPath
//получить значение ключа с диска
String getByPath(Integer key) throws IOException {
if(!keys.containsKey(key)) return null;
RandomAccessFile file = new RandomAccessFile(path, "r");
String val = getByPath(key, file);
file.close();
return val;
}
8. Т.к. ключ может вставляться неограниченное число раз, то со временем он может находится в нескольких файлах на диске одновременно.
Также, если бы LSM дерево поддерживало транзакционность, то в файлах также хранились бы разные версии одного ключа (изменения или удаления).
Для оптимизации последующего поиска применяется операция слияния нескольких файлов в один:
* Сортируем индексы по убыванию lsn
* Последовательно считываем элементы из первого индекса и записываем в новый
* Если элемент уже присутствует в объединенном индексе, то он пропускается
* Создается новый единственный файл и индекс со всеми ключами и значениями
* Старые файлы и индексы удаляются
public class LSMTree {
//....
//объединить несколько таблиц на диске в 1 большую
void merge() throws IOException {
Integer min_key = null;
Integer max_key = null;
Integer min_lsn = null;
Integer max_lsn = null;
//сортируем таблицы по убыванию lsn
//чтобы вначале были самые свежие ключи
Collections.sort(indexes, new Comparator<SSTableIndex>() {
@Override
public int compare(SSTableIndex o1, SSTableIndex o2) {
if(o1.max_lsn > o2.max_lsn) {
return -1;
} else if(o1.max_lsn < o2.max_lsn) {
return 1;
}
return 0;
}
});
SSTableIndex merge_indx = new SSTableIndex();
Integer pad = 0;
merge_indx.path = "sstable_merge.dat";
PrintWriter writer = new PrintWriter(merge_indx.path, "UTF-8");
//пробегаемся по всем индексам, чтобы слить в 1
for (SSTableIndex indx : indexes) {
if(min_lsn == null || indx.min_lsn < min_lsn) min_lsn = indx.min_lsn;
if(min_key == null || indx.min_key < min_key) min_key = indx.min_key;
if(max_key == null || indx.max_key > max_key) max_key = indx.max_key;
if(max_lsn == null || indx.max_lsn > max_lsn) max_lsn = indx.max_lsn;
RandomAccessFile file = new RandomAccessFile(indx.path, "r");
//т.к. данные в таблицах не упорядочены, это приводит к рандомным чтениям с диска
//в реальности делают упорядочнный по ключу массив, чтобы делать быстрые последовательные чтения
for(Entry<Integer, Integer> entry : indx.keys.entrySet()) {
//оставляем запись только с максимальным lsn
Integer key = entry.getKey();
if(!merge_indx.keys.containsKey(key)) {
String val = indx.getByPath(key, file);
SSItem itm = new SSItem(key, val, 0);
String itmval = itm.get();
writer.print( itmval );
merge_indx.keys.put(key, pad);
pad = pad + itmval.length();
}
}
//записываем и удаляем старые файлы
file.close();
//delete
File fd = new File(indx.path);
fd.delete();
}
merge_indx.min_lsn = min_lsn;
merge_indx.min_key = min_key;
merge_indx.max_key = max_key;
merge_indx.max_lsn = max_lsn;
writer.close();
//переименовываем к обычному имени
File fd = new File(merge_indx.path);
merge_indx.path = "sstable_" + merge_indx.max_lsn + ".dat";
File fdn = new File(merge_indx.path);
fd.renameTo(fdn);
indexes = new LinkedList<SSTableIndex>();
indexes.add(merge_indx);
} //merge
В моей реализации используется хэш массив, что дает большое число случайных чтений с диска.
В реальности данные хранят в отсотированной структуре, что позволят выполнять слияние 2 отсортированных массивов в один за линейное время используя только быстрое последовательное чтение.
Полный код класса LSM дерева можно посмотреть на github
Сборка Cloudera Hadoop не содержит никаких настроек авторизации и аутентификации, что конечно плохо, т.к. не дает возможности разделить права среди пользователей.
Опишу один из вариантов настройки авторизации и аутентификации.
5. Включаем CUSTOM аутентификацию в настройках Cloudera Manager:
прописываем наш аутентификатор в настройках:
* Ищем все настройки по паттерну "hive-site.xml" в настройках Cloudera.
Делать нужно именно через cloudera, а не напрямую в файле "hive-site.xml", т.к. менеджер переписывает файл из памяти процесса.
Нажимаем view as xml и во всех окнах и вводим
Также ставим флажки suppress parameter validation
Иначе настройки не попадут в итоговый XML файл
* Для работы также нужна включенная опция hive.server2.enable.doAs = true
Она означает, что все запросы будут идти из под пользователя, который прошел аутентификацию.
5. Задаем путь до кастомной папки с jar файлами:
Настройка: «HIVE_AUX_JARS_PATH»
Значение «/u01/jar»,
Также ставим suppress parameter validation
6. Все готово, перезапускам HIVE из консоли Cloudera
7. Теперь при аутентификации нужно указывать способ:
AuthMech=3
После того как все настроили, мы уверены, что пользователь прошел аутентификацию.
Войти без пароля больше не получится.
Дальше настраиваем авторизацию - выдачу прав пользователям на конкретные объекты.
Проще всего это сделать через расширенные права linux:
ACL авторизация
1. Включаем ACL права через Cloudera Manager
настройка "dfs.namenode.acls.enabled" = true
2. После этого можно распределять права на папки:
Сброс всех прав:
sudo -u hdfs hdfs dfs -setfacl -R -b /
Даем пользователю user1 права на создание таблиц в своей схеме
Один минус у ACL - это остается возможность выполнить DROP table, даже если нет прав доступа на чтение или запись.
Как победить эту проблему я не понял.
Так же стоит не забывать, что таким образом мы защитили только HIVE, возможность читать данные через HDFS по прежнему остались.
(Как читать данные из HDFS и HIVE через java можно посмотреть в моем github: https://github.com/pihel/java/blob/master/bigdata/Hdfs2Hive.java )
Чтобы закрыть доступ чтения через HDFS мы используем закрытие всех портов на сервере, кроме 10000 , который используется службой HIVE.
Сегодня расскажу об одном способе ускорения запросов с аналитическими функциями в субд HIVE, работающей поверх Hadoop.
Один из вариантов ускорить HIVEQL запрос - это переписать встроенную аналитическую функцию на свой упрощенный вариант.
К примеру функция ROW_NUMBER(OVER PARTITION BY c1 ORDER BY c2) имеет достаточно сложную реализацию (github) только для того чтобы посчитать номер строки в группе.
Пример запроса с row_number:
create table tmp_table stored as orc as
select v.material, v.client_id, row_number() over (partition by v.client_id order by v.clientsum desc, v.checkcount desc) as rn
from pos_rec_itm_tst v;
Можно реализовать значительно упрощенную версию подсчета номера строки в группе.
На вход функции Rank.evaluate подаем значение группы key (то что было в partition by) и инкрементируем значение счетчика counter.
Если приходит новая группа, то счетчик сбрасывается на 0, а в переменную группы "this.last_key" записывается значение новой группы:
package com.example.hive.udf;
import org.apache.hadoop.hive.ql.exec.UDF;
public final class Rank extends UDF{
private int counter;
private String last_key;
public int evaluate(final String key){
if ( !key.equals(this.last_key) ) {
this.counter = 0;
this.last_key = key;
}
return (++this.counter);
}
}
Понятно, что для правильной работы этой функции набор данных нужно предварительно отсортировать по группе партицирования "partition by", а потом по остальным полям "order by".
Пример запроса с собственной функцией:
create table tmp_table stored as orc as
select v.material, v.client_id, myrank(v.client_id) as rn from (
SELECT client_id, clientsum, checkcount, material FROM pos_rec_itm_tst
DISTRIBUTE BY client_id SORT BY clientsum desc, checkcount desc
) v;
Дополнительно сортировку в HIVE можно ускорить, если распараллелить мапперы по полю партицирования "partition by", а внутри этих групп сортировать по полям из "order by".
За счет параллельности мы опять же ускорим сортировку.
Чтобы создать такую функцию в HIVE нужно скомпилировать ее из java исходников:
Basic compression – работает только при direct path (append) вставке
Представляет из себя дедублицирование данных.
При Update строка становится мигрированной и хранится уже не сжатой.
Oltp compression – работает при любых вставках и требует наличия опции advanced compression.
Представляет из себя дедублицирование данных.
При не «direct path» строка сначала вставляется несжатой, при накоплении % несжатых записей в блоке = PCTFREE, блок сжимается и т.д.:
При Update строка становится мигрированной и хранится сначала не сжатой, но потом при накоплении PCTFREE % несжатых записей, блок аналогично сжимается.
HCC - hybrid columnar compression
работает только с «Exadata или Oracle ZFS Storage Appliance или either the Pillar Axiom или Oracle FS1 storage array».
Oracle хранит компрессированную колонку в виде связки блоков (как мигрированная строка), что оставляет возможность быстрого доступа к колонке по rowid и создание индексов!.
Также требуется direct path (append) вставка.
Внутреннее устройство:
Строки данных бьются на compression unit (cu) – это достаточно большая сущность (32 КБ) и со стороны Oracle рассматривается как 1 блок.
Детальная структура CU:
CU в заголовке содержит указатели на колонки. А блоки внутри CU указатели на строки.
Т.к. все строки поделены на CU, внутри которых последовательно хранятся колонки, то добавление колонок к запросу не увеличивает число чтений (даже если строки из разных CU, число чтений будет кратно число блоков в CU * кол-во запрашиваемых CU):
Чтение 1 блока дает 417 чтений:
select /*+ MONITOR */ id, num_1000000 from t_qh where id in( 5123456);
И чтение из 2 разных блоков тоже дает 417 чтений, т.к. оба этих блока входят в 1 CU:
select /*+ MONITOR */ id, num_1000000 from t_qh where id in( 5123456, 6114557 );
Поддержка DML:
- Блокировка по умолчанию происходит на уровне CU. Если нужна блокировка на уровне строки, то таблицу нужно создавать с директивой «ROW LEVEL LOCKING», которая расширяет заголовок CU под флаги блокировок всех строк всех блоков.
- При обновлении строки, она мигрирует в другой блок и помечается сжатой как OLTP, в не зависимости от степени сжатия раньше (см. описание выше)
Сжатие колонок
Обычные способы сжатия, а не алгоритмы дедубликации:
Query Low – LZO (4x)
Данные перед вставкой не сортируются
Query High – gzip (6x)
Во всех других случаях данных сортируются в рамках одного CU, чтобы достичь большей компрессии (по одному из столбцов?)
Archive Low – gzip high (7x)
Archive High – bzip2 (12x)
Т.к. HCC заточено на хранилища данных, то максимальный выигрыш дают смарт сканы, т.к. разархивация происходит на стороне exadata cells. В случае индексного доступа разархивация происходит уже в БД (причем всего CU!):
Смарт скан, отрицательный offloading - возвращено больше, чем считано:
Oracle хранит данные сразу в 2 форматах: строковый и колоночный. Это могут быть как таблицы, так и matview на наборе таблиц.
Загонять данные в колонки нужно вручную.
В inmemory можно поместить часть столбцов или разную степень для разных колонок.
Размер IMCU = 1МБ ( blogs.oracle.com ) см. imcu_addr.v$im_header
Данные в IMCU всегда хранятся в порядке вставки (rowid) -
docs.oracle.com
Пример:
SELECT cust_id, time_id, channel_id
FROM sales
WHERE prod_id =5;
Данные из колонки «prod_id» фильтруются, в результате чего определяются позиции на которых находятся искомые данные. Т.к. данные в колонках лежат в том же порядке (включая null), то по этим номерам позиций забираются соответствующие значения из связанных колонок (time_id, chanel_id)
Основные понятия IM HCC
Local dictionary CU
хэш массив уникальных значений в CU (в виде чисел)
min/max значение в колонке CU
«IM storage index» - для отфильтровывания CU
IMCU index хранятся прямо в заголовке CU.
SMU (Snapshot Metadata Unit) = 64КБ – метаданные о IMCU - информация о инвалидации данных в IMCU при DML (транзакционный журнал).
Для DML по прежнему используется буферный кэш, но в SMU помещается информация, что rowid был инвалидирован.
Т.е. чем больше DML, тем хуже работает IM
Repopulation – периодическое обновление измененных данных в IMCU из буферного кэша (при накоплении определенного объема). На время этой операции IMCU отключаются, используется стандартный механизм доступа.
Ручной запуск:
EXEC DBMS_INMEMORY.POPULATE('SH', 'CUSTOMERS');
При exchange partition чтобы не потерять данные IM нужно собрать данные src таблицы в IM. Тогда обмен произойдет как у таблицы, так и у IM хранилища.
При direct path (+append) вставке происходит автоматическая фоновая репопуляция.
IM expression unit
В IM кроме обычных колонок могут хранится виртуальные выражения (как колонки, там и предрасчитанные на основе статистики вызова - «IM expression statistic store»), они будут также обновляться при repopulation.
IM expression statistic store
Дополнительное сохранение агрегированных данных SELECT, WHERE, GROUP BY если они часто вызываются и требуют больших расходов на расчет.
SIMD – векторная обработка колонок
Т.к. данные для фильтрации хранятся в виде колонки-вектора, то для фильтрации можно использовать векторные возможности CPU.
Векторная операция – это когда за 1 такт процессора происходит сравнение не одной переменной, а целого вектора значений (к примеру 8)
Раньше эта технология часто использовалась в графике, например при работе с RGB значениями, цвет пикселя можно было сменить за 1 такт CPU, теперь эти технологии нашли применение и в СУБД.
Компрессия:
* «MEMCOMPRESS FOR QUERY LOW» - алгоритм по умолчанию
Похоже на дедублицирование: словарь + обнаружение повторов + замена повтором на бит ссылку
(oracle.com/technetwork )
* «MEMCOMPRESS FOR CAPACITY LOW» - Используется проприетарный алгоритм OZIP, как расширение поверх «MEMCOMPRESS FOR QUERY LOW». Нужно разжатие перед выполнением WHERE, но может выполняться прямо на CPU (нужны специальные сервера с SQL in Silicon)
IM JOIN
SELECT v.year, v.name, s.sales_price
FROM vehicles v, sales s
WHERE v.name = s.name;
Обычный джойн выполняется так:
Т.е. большая часть работы — это преобразование колоночного вида в строковое хранилище pga.
Над join можно произвести первую оптимизацию — bloom filter, т. е. испольлзуя данные 1 таблицы откинуть лишние CU еще до join.
Для устранения необходимости преобразования колоночного вида в строковый можно подготовить что-то типа join индекса в IM:
CREATE INMEMORY JOIN GROUP deptid_jg (hr.employees(department_id),hr.departments(department_id));
В индексе сохраняются сочетания значений «Local dictionary CU» нужных колонок таблиц, где значения = указатели на нужные CU.
В итоге JOIN будет выполняться как фильтр большей таблицы по данным меньшей:
* фильтруем колонку левой таблицы
* получаем цифровые значения строк левой таблицы из “Local dictionary CU”
* сохраняем этот массив в PGA
* применяем фильтр к правой таблице на основе нашего «INMEMORY JOIN GROUP» где хранится связка левых CU с правыми CU
В итоге получается выполнение join без преобразования колонок в строки и фильтрация идет по обычному массиву (не хэш), т. е. без потребления дополнительного CPU для хэширования и проблемы хэш массива: устранения коллизий.
IM Vector Group BY
SELECT c.customer_id, s.quantity_sold, s.amount_sold
FROM customers c, sales s
WHERE c.customer_id = s.customer_id
AND c.country_id = 'FR';
IM Vector group by есть общее со star transformation – преобразование JOIN в фильтрацию фактовой таблицы измерениями:
* фильтруем колонку левой таблицы
* Создаем массив уникальных значений левой таблицы: 0 — нет значения, 1,2,N существующие уникальные значения
* созданные массивы в векторном режиме применяются над фактовой таблицой.
План будет выглядеть так:
SQL_ID 0yxqj2nq8p9kt, child number 0
-------------------------------------
SELECT t.calendar_year, p.prod_category, SUM(quantity_sold) FROM
times t, products p, sales f WHERE t.time_id = f.time_id AND
p.prod_id = f.prod_id GROUP BY t.calendar_year, p.prod_category
Plan hash value: 2377225738
------------------------------------------------------------------------------------------------------
|Id| Operation | Name |Rows|Bytes|Cost(%CPU)|Time|Pstart|Pstop|
------------------------------------------------------------------------------------------------------
| 0|SELECT STATEMENT | | | |285(100)| | | |
| 1| TEMP TABLE TRANSFORMATION | | | | | | | |
| 2| LOAD AS SELECT |SYS_TEMP_0FD9D6644_11CBE8| | | | | | |
| 3| VECTOR GROUP BY | | 5| 80 | 3(100)|00:00:01| | |
| 4| KEY VECTOR CREATE BUFFERED | :KV0000 |1826|29216| 3(100)|00:00:01| | |
| 5| TABLE ACCESS INMEMORY FULL | TIMES |1826|21912| 1(100)|00:00:01| | |
| 6| LOAD AS SELECT |SYS_TEMP_0FD9D6645_11CBE8| | | | | | |
| 7| VECTOR GROUP BY | | 5| 125 | 1(100)|00:00:01| | |
| 8| KEY VECTOR CREATE BUFFERED | :KV0001 | 72| 1800| 1(100)|00:00:01| | |
| 9| TABLE ACCESS INMEMORY FULL | PRODUCTS | 72| 1512| 0 (0)| | | |
|10| HASH GROUP BY | | 18| 1440|282 (99)|00:00:01| | |
|11| HASH JOIN | | 18| 1440|281 (99)|00:00:01| | |
|12| HASH JOIN | | 18| 990 |278(100)|00:00:01| | |
|13| TABLE ACCESS FULL |SYS_TEMP_0FD9D6644_11CBE8| 5| 80 | 2 (0)|00:00:01| | |
|14| VIEW | VW_VT_AF278325 | 18| 702 |276(100)|00:00:01| | |
|15| VECTOR GROUP BY | | 18| 414 |276(100)|00:00:01| | |
|16| HASH GROUP BY | | 18| 414 |276(100)|00:00:01| | |
|17| KEY VECTOR USE | :KV0000 |918K| 20M|276(100)|00:00:01| | |
|18| KEY VECTOR USE | :KV0001 |918K| 16M|272(100)|00:00:01| | |
|19| PARTITION RANGE ALL | |918K| 13M|257(100)|00:00:01|1|28|
|20| TABLE ACCESS INMEMORY FULL| SALES |918K| 13M|257(100)|00:00:01|1|28|
|21| TABLE ACCESS FULL |SYS_TEMP_0FD9D6645_11CBE8| 5 | 125| 2 (0)|00:00:01| | |
------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
11 - access("ITEM_10"=INTERNAL_FUNCTION("C0") AND "ITEM_11"="C2")
12 - access("ITEM_8"=INTERNAL_FUNCTION("C0") AND "ITEM_9"="C2")
Note
-----
- vector transformation used for this statement
IM RAC
Можно продублировать IMCU на всех нодах «DUPLICATE ALL» или разделить таблицу (DISTRIBUTE ) — часть на 1 ноде, часть на другой:
* по партициям «DISTRIBUTE BY PARTITION »
* по диапазону rowid “DISTRIBUTE BY ROWID RANGE”
- распределенная файловая система. Это значит, что данные файла распределены по множеству серверов.
* hdfs лучше работает с небольшим числом больших файлов/блоков
* один раз записали, много раз считали
* можно только целиком считать, целиком очистить или дописать в конец (нельзя с середины)
* файлы бьются на блоки split (к примеру 64мб)
** размер блока выбирается так, чтобы нивилировать время передачи блока по сети (если сеть быстрая, то блок можно поменьше, если медленная, то больше)
* все блоки реплицируются с фактором 3 поумолчанию (хранятся в 3 копиях на разных серверах)
** это обеспечивает высокую пропускную способность, но не скорость реакции
1. input file: split 1 + split 2 + split 3 (блоки файла). Каждый сплит хранится на своем сервере кластера.
2. mapper:
* на каждый split N создается worker для обработки
* worker выполяется на сервере, где находится блок
* workerы не могут обмениваются между собой данными
** т.е. mapper подходит для независимых данных, которые легко побить на части.
зависимые данные (типа архива zip) нельзя побить на части в mapper:
все блоки (split) будут переданы в один mapper
* в случае ошибки процесс рестратует на другой копии блока hdfs
* combine - (необязательный шаг) - reducer внутри mappera агрегирующие данные в меньшее число данных (ключ менять нельзя)
** агрегирует только данные одного маппера
* partition - (необязательный шаг) - определение куда отправится ключ (поумолчанию hash(k) mod N , где N - число reducer )
3. результат mapper записывается в виде ключ значение {k->v} в циклический буфер в памяти, конец списка пишется на локальный диск сервера с worker
** это сделано в целях производительности, чтобы не реплицировать
** но в случае ошибки, данные нельзя будет восстановить и потребует рестартовать mapper
4. данные из {k->v} расходятся на сервера reduccer на основе ключа.
Т.е. данные с разных mapperов но с одним key попадут в один reducer
5. Результат reducer складываются в hdfs. Число файлов = число reducer
Инструмент для быстрого прототипирования map reduce задач.
можно писать python программы заготовки, общение маппера с редусером проиходит чреез stdin/out.
Данные передаются как текст разделенный табом
word count
#!/usr/bin/python
import sys
for line in sys.stdin:
for token in line.strip().split(" "):
if token: print(token + '\t1')
#!/usr/bin/python
import sys
(lastKey, sum)=(None, 0)
for line in sys.stdin:
(key, value) = line.strip().split("\t")
if lastKey and lastKey != key:
print (lastKey + '\t' + str(sum))
(lastKey, sum) = (key, int(value))
else:
(lastKey, sum) = (key, sum + int(value))
if lastKey:
print (lastKey + '\t' + str(sum))
public class WordCountJob extends Configured implements Tool {
static public class WordCountMapper extends Mapper < LongWritable, Text, Text, IntWritable > {
private final static IntWritable one = new IntWritable(1);
private final Text word = new Text();
@Override
protected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {
//разбиваем строку (key) на слова и передаем пару: слово, 1
StringTokenizertokenizer = new StringTokenizer(value.toString());
while (tokenizer.hasMoreTokens()) {
text.set(tokenizer.nextToken());
context.write(text, one);
}
} //map
} //WordCountMapper
static public class WordCountReducer extends Reducer < Text, IntWritable, Text, IntWritable > {
@Override
protected void reduce(Text key, Iterable < IntWritable > values, Context context) throws IOException, InterruptedException {
//в редусер приходят все единицы от одного слова
intsum = 0;
for (IntWritable value: values) {
sum += value.get();
}
context.write(key, new IntWritable(sum));
} //reduce
} //WordCountReducer
@Override
public int run(String[] args) throws Exception {
Job job = Job.getInstance(getConf(), "WordCount");
//класс обработчик
job.setJarByClass(getClass());
//путь до файла
TextInputFormat.addInputPath(job, new Path(args[0]));
//формат входных данных (можно отнаследовать и сделать собственный)
job.setInputFormatClass(TextInputFormat.class);
//классы мапперов, редусееров, комбайнеров и т.д.
job.setMapperClass(WordCountMapper.class);
job.setReducerClass(WordCountReducer.class);
job.setCombinerClass(WordCountReducer.class);
//выходной файл
TextOutputFormat.setOutputPath(job, new Path(args[1]));
job.setOutputFormatClass(TextOutputFormat.class);
job.setOutputKeyClass(Text.class);
job.setOutputValueClass(IntWritable.class);
return job.waitForCompletion(true) ? 0 : 1;
} //run
public static void main(String[] args) throws Exception {
int exitCode = ToolRunner.run( new WordCountJob(), args);
System.exit(exitCode);
} //main
} //WordCountJob
Такая программа будет тратить все время на передачу данных от маппера к редусеру.
Её можно усовершенствовать несколькими способами:
* Сделать комбайнер - чтобы данные из одного маппера были сагрегированы там.
- не обязательно вызывается
+/- агрегирует данные только одного вызова маппера (одной строки)
* хэш аггегировать внутри маппера:
+ обязательно выполнится
+/- агрегирует данные только одного вызова маппера (одной строки)
- нужно следить за размером хэш массива
* хэш массив сверху маппера, а внутри маппера обрабатывать
+ обязательно выполнится
+ агрегирует все вызовы маппера (сплита)
- нужно следить за размером хэш массива
// на вход подаются элементы из двух множеств A и B
class Mapper
method Map(rowkey key, value t)
Emit(value t, string t.SetName) // t.SetName либо ‘A‘ либо ‘B'
class Reducer
// массив n может быть [‘A'], [‘B'], [‘A' ‘B‘] или [‘B', ‘A']
method Reduce(value t, array n)
if n.size() = 1 and n[1] = 'A'
Emit(value t, null)
* hash join
class Mapper
method Initialize
H = new AssociativeArray : join_key -> tuple from A //хэшируем меньшую таблицу целиком в память
A = load()
for all [ join_key k, tuple [a1, a2,...] ] in A
H{k} = H{k}.append( [a1, a2,...] )
method Map(join_key k, tuple B)
for all tuple a in H{k} //ищем в A соответствие ключа из B
Emit(null, tuple [k a B] ) //если нашли, то записываем
оптимальное представление в виде списка смежности, т.к. матрица смежности занимает слишком много места
* поиск кратчайшего пути
** обычный алгоритм - дейкстра
** поиск в ширину (bfs)
на невзвешенном графе (нет связей назад):
- Останавливаемся, как только расстояния до каждой вершины стало известно
- Останавливаемся, когда пройдет число итераций, равное диаметру графа
на взвешенном графе (есть обратные связи):
- Останавливаемся, после того, как расстояния перестают меняться
* PR = a (1/N) + (1-a)* SUM( PR(i) / C(i) )
** N - начальное число точек в графе
** C - число исходящих точек
** a - вероятность случайного перехода
** pr решается только приблизительно:
- останавливаем, когда значения перестают меняться
- фиксированное число итерации
- когда изменение значение меньше определенного числа
* проблемы
** необходимость передавать весь граф между всеми задачами
** итеративный режим, т.е. переход на следующий этап, когда все параллельные задачи выполнятся
* оптимизации:
** inmemory combining - агрегируем сообщения в общем массиве
** партицирование - смежные точки оказались на одном маппере
** структуру графа читать из hdfs, а не передавать + партицирование
высокоуровневый язык + компилятор в mapreduce
используется для быстрого написания типовых map-reduce задач
основные составляющие:
* field - поле
* tuple - кортеж (1, "a", 2)
* bag - коллекция кортежей {(), ()}
** коллекции могут содержать разное кол-во полей в кортеже (также они могут быть разных типов)
word count:
input_lines = LOAD 'file-with-text' AS (line:chararray);
words = FOREACH input_lines GENERATE FLATTEN(TOKENIZE(line)) AS word;
filtered_words = FILTER words BY word MATCHES '\\w+';
word_groups = GROUP filtered_words BY word;
word_count = FOREACH word_groups GENERATE COUNT(filtered_words) AS count,
group AS word;
ordered_word_count = ORDER word_count BY count DESC;
STORE ordered_word_count INTO ‘number-of-words-file';
join
//Загрузить записи в bag #1
posts = LOAD 'data/user-posts.txt' USING PigStorage(',') AS (user:chararray,post:chararray,date:long);
//Загрузить записи в bag #2
likes = LOAD 'data/user-likes.txt' USING PigStorage(',') AS (user:chararray,likes:int,date:long);
userInfo = JOIN posts BY user, likes BY user;
DUMP userInfo;
sql подобный язык hivesql поверх hadoop
основные составляющие - как в бд
метаданные могут храниться в mysql /derby
* создание таблицы
hive> CREATE TABLE posts (user STRING, post STRING, time BIGINT)
> ROW FORMAT DELIMITED
> FIELDS TERMINATED BY ','
> STORED AS TEXTFILE;
* при нарушении схемы ошибки не будет, вставится NULL
join
hive> INSERT OVERWRITE TABLE posts_likes
> SELECT p.user, p.post, l.count
> FROM posts p JOIN likes l ON (p.user = l.user);
word count
CREATE TABLE docs (line STRING);
LOAD DATA INPATH 'docs' OVERWRITE INTO TABLE docs;
CREATE TABLE word_counts AS
SELECT word, count(1) AS count FROM
(SELECT explode(split(line, '\s')) AS word FROM docs) w
GROUP BY word
ORDER BY word;
* Масштабирование:
** мастер-слейв: распределение нагрузки cpu, io остается общим
** шардинг: деление данных таблицы по серверам: распределение io, cpu Общее
* cap theorem - достигается только 2 из 3
** consistency - непротиворечивость
Чаще всего жертвует строгой целостностью в текущий момент, на целостность в конечном счете
** aviability - доступность
** partioning - разделение данных на части
* типы:
** ключ-значение
** колоночная
** документоориентировання
** графовая
- поколоночная база
** строки в таблицах шардируются на сервера
*** строки хранятся в отстортированном виде, чтобы можно было искать по серверам
*** список шардов хранится в HMaster
через него определяется сервер для чтений, а дальше чтение идет уже напряму с него миную hmaster
! возможная точка отказа
** столбцы объединяются в column family
*** каждая такая группа сохраняется также в отдельный файл
*** для всей группы задается степень сжатия и другие физические настройки
** изменение/удаление происходит через вставку нового значения в колонку с TS
*** при select выбираются последние 3 изменения (если в колонке не было изменений, то берется предыдущая максимальная версия)
** промежуточные данные хранятся в memstore сервера и логе изменений
*** периодически данные из памяти скидываются на hdfs
** hfile - мапится в файл hdfs, который также splitit'ится на разные сервера
** сжатие файлов хранилища:
*** объединение файлов CF в один
*** очистка от удаленных записей
Массовость - деление данных на сервера по:
* по семейству колонок
* по диапазону ключей
* по версии строки
* сам файл разбивается в hdfs на сплиты
отличия:
** есть sql, а не только java api
** CF имеют иерархичность и могут также объединяться в группы по какомуто признаку
** настраевая consistency от самой строгой - ожидание отклика всех серверов, то записи без проверок
** нет единой точки отказа hmaster, данные делятся по диапазону
** но усложняет деление и поиск данных
* greenplum - классическая колоночная бд, с шардирование данных на основе pgsql
** есть поддержка sql
* Преимущества перед hadoop:
1. Необязательно сохранять промежуточные результаты в HDFS при итеративной разработке. Данные можно хранить в памяти.
2. Необязательно чередовать map-reduce, можно делать несколько reducer подряд
3. Операции в памяти (вкллючая синхронизацию между серверами), а не через hdfs
4. Возможность загрузить данные в распределенную память, а потом делать обработку (каждому mapper уже не надо считывать данные из hdfs)
* В основе может лежать любой вид хранилища данных
* Архитектура, как в hadoop: name node (driver) + worker
* Основная составляющая вещь - RDD:
** объект партицируется
** каждая партиция имеет произвольное хранение: память, диск, hdfs и т.д.
*** Для хранения данных в памяти используется LRU буфер.
Старые, редко используемые данны вытесняются в медленное хранилище
** объект неизменяем (изменение создает новый объект)
** rdd распределена по серверам
* Программа состоит из однонаправленного графа операций без циклов
Виды зависимостей в графе:
** Narrow (узкая) - переход 1 партииции в 1 другую
** wide (широкая) - переход 1 (N) партиций в N (1)
* Восстановление в случае падения:
- нет репликации как в hdfs
+ для воостановления используется перезапуск
** если потерялись данные из одной партиции в Narrow связи, то восстанавливается только она из предыдущей партиции
** если в wide то перезапускаются все партиции (т.к. связ не 1 к 1).
Результат wide поумолчанию сохраняется на диск.
** Если есть шанс потерять данные, а цепочка длинная, то лучше самим самостоятельно сохранять промежуточные результаты на диск.
* Типы операции состоят из:
** Трансформация - не запускают работу
map, filer, group, union, join ....
** Действий - запускают работу (все трансформации в графе до этого графа)
count, collect, save, reduce
val file = sc.textFile("hdfs://...")
val sics = file.filter(_.contains("MAIL"))
val cached = sics.cache()
val ones = cached.map(_ => 1)
val count = ones.reduce(_+_)
val file = sc.textFile("hdfs://...")
val count = file.filter(_.contains(“MAIL")).count()
или
val file = spark.textFile("hdfs://...")
val counts = file.flatMap(line => line.split(" "))
.map(word => (word, 1))
.reduceByKey(_ + _)
counts.saveAsTextFile("hdfs://...")
* Переменные для обмена данными между серверами
** broadcast variables - переменная только для чтения
val broadcastVar = sc.broadcast(Array(1, 2, 3))
...
broadcastVar.value
** Accumulators - счетчики
val accum = sc.accumulator(0)
accum += x
accum.value
планировщик ресурсов, которые избавляет от недостатков классического MR:
* жесткое разделенеи ресурсов: можно освободить ресурсы от mapper после их полного выполнения и отдать все ресурсы reducer
* возможность разделять ресурсы не только между MR Задачами, но и другими процессами
* разделение происходит в понятии: озу, cpu, диск, сеть и т.д.
* он же производит запуск задач (не только MR) и восстанавливает в случае падения
* для работы нужны вспомогательные процессы:
** appserver - получение комманд от клиента
** resource server - север для выделяющий ресурсы
** node server - сервер для запуска задач и отслеживания за ними (на каждом сервере)
Нововведение Oracle 12.1 - приблизительный подсчет уникальных значений ( APPROX_COUNT_DISTINCT ~= count distinct ).
Классический подход к расчету числа уникальных значений предполагает создание хэш массива, где ключ = колонке таблицы, а в значении число совпадений.
Число элемнтов в хэш массиве будет равно числу уникальных данных в колонке таблицы:
class RealDist {
HashMap words;
public RealDist() {
words = new HashMap();
}
public void set(String word) {
if (!words.containsKey(word)) {
words.put(word, 1);
} else {
words.put(word, words.get(word) + 1);
}
} //set
public int get() {
return words.size();
} //get
} // RealDist
Этот способ всем хорош, пока у нас достаточно памяти под хранение хэш массива.
При росте размера данных время и потребляемые ресурсы начинают катастрофически расти.
Пример со страницы antognini с разным числом уникальных значений на 10 млн. строк:
CREATE TABLE t
AS
WITH
t1000 AS (SELECT /*+ materialize */ rownum AS n
FROM dual
CONNECT BY level <= 1E3)
SELECT rownum AS id,
mod(rownum,2) AS n_2,
mod(rownum,4) AS n_4,
mod(rownum,8) AS n_8,
mod(rownum,16) AS n_16,
mod(rownum,32) AS n_32,
mod(rownum,64) AS n_64,
mod(rownum,128) AS n_128,
mod(rownum,256) AS n_256,
mod(rownum,512) AS n_512,
mod(rownum,1024) AS n_1024,
mod(rownum,2048) AS n_2048,
mod(rownum,4096) AS n_4096,
mod(rownum,8192) AS n_8192,
mod(rownum,16384) AS n_16384,
mod(rownum,32768) AS n_32768,
mod(rownum,65536) AS n_65536,
mod(rownum,131072) AS n_131072,
mod(rownum,262144) AS n_262144,
mod(rownum,524288) AS n_524288,
mod(rownum,1048576) AS n_1048576,
mod(rownum,2097152) AS n_2097152,
mod(rownum,4194304) AS n_4194304,
mod(rownum,8388608) AS n_8388608,
mod(rownum,16777216) AS n_16777216
FROM t1000, t1000, t1000
WHERE rownum <= 1E8;
Скорость вычислений классическим способом падает вместе с ростом числа уникальных значений:
Пропорционально времени работы растет и потребление PGA памяти под хранение хэш массива:
Чтобы решить проблему производительности/памяти и при этом получить приемлемый результат, можно применить приблизительный расчет числа уникальных значений.
Как и bloom filter он основан на вероятностных хэш значениях от данных.
1. От каждого значения берется произвольная хэш функция
public static int fnv1a(String text) {
int hash = 0x811c9dc5;
for (int i = 0; i < text.length(); ++i) {
hash ^= (text.charAt(i) & 0xff);
hash *= 16777619;
}
return hash >>> 0;
} //fnv1a
2. У каждого хэш значения определяется ранк первого ненулевого бита справа.
// позиция первого ненулевого бита справа
public static int rank(int hash, int max_rank) {
int r = 1;
while ((hash & 1) == 0 && r <= max_rank) {
r++;
// смещаем вправо, пока не дойдет до hash & 1 == 1
hash >>>= 1;
}
return r;
} //rank
Вероятность того, что мы встретим хеш с рангом 1 равна 0.5, с рангом 2 — 0.25, с рангом r — 1 / 2ранг
Если запоминать наибольший обнаруженный ранг R, то 2R сгодится в качестве грубой оценки количества уникальных элементов среди уже просмотренных.
Такой подход даст нам приблизительное число уникальных значений, но с сильной ошибкой.
Для данного алгоритма есть усовершенствованный вариант HyperLogLog:
а. От битового представления хэш берется 8 первых левых бит. Они становятся ключом массива (2^8 = 256 значений)
public void set(String word) {
int hash = fnv1a(word);
// убираем 24 бита из 32 справа - остается 8 левых
// (=256 разных значений)
int k = hash >>> 24;
// если коллизия, то берем наибольший ранк
hashes[k] = Math.max(hashes[k], rank(hash, 24));
} // count
б. Над массивов вычисляется формула:
где am - корректирующий коэффициент, m - размер массива = 256, M[] - массив ранков (hashes)
Для погрешности в 6.5% числитель этой формулы будет равен константе = 47072.7126712022335488.
Остается в цикле возвести 2 в -степень максимального ранка из каждого элемента массива:
public double get_loglog() {
double count = 0;
for (int i = 0; i < hashes.length; i++) {
count += 1 / Math.pow(2, hashes[i]);
}
return 47072.7126712022335488 / count;
} //get_loglog
Данный алгоритм уже дает приемлемый результат на больших данных, но серьезно ошибается на небольшом наборе.
Для небольших значение применяется дополнительная математическая корректировка:
public int get() {
long pow_2_32 = 4294967296L;
double E = get_loglog();
// коррекция
if (E <= 640) {
int V = 0;
for (int i = 0; i < 256; i++) {
if (hashes[i] == 0) {
V++;
}
}
if (V > 0) {
E = 256 * Math.log((256 / (double) V));
}
} else if (E > 1 / 30 * pow_2_32) {
E = -pow_2_32 * Math.log(1 - E / pow_2_32);
}
// конец коррекции
return (int) Math.round(E);
} //get
Проведенных тест на 1-2 томах войны и мира показал результаты:
* реальное количество уникальных слов = 3737
* приблизительное число уникальных слов основываясь только на максимальном ранке первого ненулевого бита справа = 16384
* приблизительное число уникальных слов по формуле из п. б на массиве из 256 элементов = 3676
* приблизительное число уникальных слов по формуле и корректировке = 3676
При ошибке числа уникальных значений в 6,1% мы затратили константное число памяти под массив из 256 элементов, что в разы меньше, чем при обычном хэш массиве.
Полный исходный код на java можно посмотреть на github
Эти ограничения реализуют главное свойство красно-чёрных деревьев: путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа. 
В таком дереве каждый узел может содержать от 1 до 3 значений и от 2 до 4 указателей на потомков. 
Сегодня расскажу об одном способе ускорения запросов с аналитическими функциями в субд 
