Serguey Zefirov (thesz) wrote,

Возвращаясь к LevelDB.

Делая хранилище, реализовал Crit-Bit trees (близкий аналог, на самом деле - у меня C#, а дизайн по ссылке для C) и на их основе приоритетную очередь, где приоритет - лексикографический порядок ключей (как у memcmp).

Получил ускорение, как и ожидал. Пока измерил для небольшого объема, 120000 вставок. Скорость возросла на 40% (458 супротив 771 миллисекунды). Это хорошо объяснимо - при вставке в очередь проход по ключу осуществляется всего один раз.

Я понял смысл выбора дизайна LevelDB - они позволяют сравнивать записи, не конвертируя их в подходящее для memcmp представление. Это нормально, может быть, даже ускоряет работу. Но будучи совмещенным с другим выбором - список с пропусками для структуры быстрого поиска, - делает невозможной алгоритмическую оптимизацию, которая доступна для memcmp-совместимого ключа и crit-bit trees.
Tags: google, базы данных, программирование
  • 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 

  • 4 comments