Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Category:

Довольно неправильное мнение об одной устаревшей статье.

Вот тут.

ARIES на самом деле сборник рецептов "как построить хранилище БД" для состояния дел до 1992 года. После 1992 года тоже кое-что придумали. Точнее, пересмотрели то, что уже имеется.

Итак, приступим. Прямое использование B+-tree выгодно, когда вставок либо заметно меньше чтений, либо они часто следуют по порядку возрастания ключа. В противном случае локальность записей становится мала и B+-tree деградирует, даже чтение становится медленным (не из последовательных адресов). Ситуация с большим числом записей не по порядку нормальна для многих задач из жизни и обязательно встретится, если есть хоть какие-то нетривиальные индексы.

Получается, что B+-tree это не совсем динамическая структура данных и что необходимо прибегать к логарифмическому методу. Всё это выливается в структуру типа LSM-дерева. LSM-дерево - набор B+-деревьев увеличивающегося размера, в деревьях большего размера лежат более старые данные, иногда производится слияние деревьев с перезаписью новых данных, если более новая информация переходит некий порог по объёму. При слиянии деревьев данные из нового дерева вставляются по порядку, приводя к лучшей локальности записи и меньшей фрагментации данных.

Что приятно, это то, что логарифмический метод применим гораздо шире, чем хранение индексированных данных в БД. Его можно применить и к данным типа GIS, многомерным структурам поиска. Один пример дан в лекции по логарифмическому методу (диаграммы Вороного), но есть ещё одна медленная структура - k-d дерево. Поиск быстрый, построение медленное. Её ускоряют ровно таким же методом - разбив на несколько уровней.

Что интересно, статья про логарифмический метод 1980 года.

Для поддержания высоких уровней изоляции и возможности всё ещё остаться в своём уме, используется Multi-Version Concurrency Control, MVCC - ведение нескольких структур данных с копированием при записи. При commit транзакции записывается корень новых данных. Ссылка, кстати, ведет прямо на список баз данных, что используют MVCC. При MVCC лог не особо и нужен - можно просто хранить несколько последних корней дерева. Это потребует некоторого переосмысления структуры БД - скорее всего, всё надо хранить в одном файле, - но всё ещё не сложно реализовать.

Последнее про базы - БерклиДиБи на один записанный байт записывает 10 (десять) байт лога.

Про параллельное выполнение транзакций. Если упорядочить транзакции, то выполнение можно сделать детерминированным и легко разделяемым по репликам. Что интересно, лог также упрощается или даже упраздняется. В любом случае он становится высокоуровневым, а не байто-ориенированным, как в ARIES.

По сумме вышесказанного, я считаю, что ARIES сегодня это очень плохо. Используйте что-нибудь другое. Целее будете.

Последнее - про квантовые компьютеры, там в комментариях было "открыли новое". Дам ещё одну ссылку: http://dr-klm.livejournal.com/123882.html

В комментариях по ссылке на dr_klm есть понятное объяснение, почему квантовые вычисления обязаны упереться в проблему масштабирования и вряд-ли смогут выйти за пределы нескольких десятков ку-бит.

И вот ещё. Не всё там гладко. В первых версиях обычные компьютеры вообще побивали D-Wave, даже на симуляции квантовых процессов!

(D-Wave не имеет связей атомов "все со всеми", поэтому он не квантовый компьютер, а "квантовый оптимизатор")

Это я слегка злорадствую, на самом деле. ;)
Tags: ЖЖ, алгоритмы, базы данных, квантовые вычисления
Subscribe

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 5 comments