Продолжаем срывать покровы в кодировании информации.
http://blog.pikosec.com/?p=120Эта структура данных представляет собой ассоциативный массив – набор пар ключ-значение. Вставлять в эту структуру можно только отсортированые данные. Однажды вставив элемент, его невозможно удалить. Невозможно из структуры получить количество вставленных пар ключ-значение. Невозможно сделать выборку по диапазону ключей. Запросив существующий ключ мы гарантировано получим его значение. Запросив несуществующий ключ – мы получим муссор.
Загадочные свойства, не правда ли ? В чем смысл такой структуры и почему она себя так ведет ? Это неоттесаный бриллиант. В то время как другие структуры кодируют данные для удобного поиска месторасположением или хешфункцией – эта структура кодирует данные переходами. Помните на заре программирования, программа в которой используются сотни операторов GoTo – живет своей жизнью. Она настолько сложна и столько содержит в себе состояний, что отладить ее практичеси невозможно. Представьте что в этой структуре таких переходов сотни тысяч, миллионы …. Каждая ячейка это переход, откудато кудато. И они кодируют данные.
Миллиард случайно сгенерированых 16 байтных ключей в контейнере ? Ерунда, любой ключ будет найден ровно в четыре касания. Тогда как обычному бинарному дереву таких касаний понадобится тридцать штук. При этом этой структуре понадобится памяти столькоже, сколько понадобится если эти пары ключ-значение хранить связным списком.
Вот так. VymaDB отошла от той идеальной, первобытной структуры. Она оптимизирована на скорость вставки, проверку существующих ключей, сканы по диапазону. Словом всё то, что нужно типичном потребителю. Но она уже не так удивительна и загадочна как та, первобытная структура, которая кодирует информацию бесконечным количеством запутаных переходов.