Serguey Zefirov (thesz) wrote,

Продолжая тему про выбор структур и алгоритмов.

Доделал-таки внесение приоритетных очередей на Crit-Bit trees для LSM дерева. До этого у меня была приоритетная очередь примерно похожая на то, что в LevelDB.

Что я могу сказать. Вставка ускорилась от 40 процентов (на 120 тысячах) до трех, и даже чуть более, раз (на миллионе, хотя и с другой природой тестовых данных).

Чтение ускорилось. От 20% до тоже чуть более трех раз.

Все ключи короткие - 10 байт и менее. То есть, это даже не хэши.

В общем, если кто реализует свое LSM-дерево, то рекомендую порядок сортировки по memcmp и использовать crit-bit trees.
Tags: базы данных
  • 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 

  • 1 comment