GitHub - openacidslim Дивовижно космічно ефективна триє в Голангу (11 біткей; 100 nsget)

Тонкий - напрочуд просторові типи даних у Golang

космічно

Slim - це колекція напрочуд просторових типів даних із відповідними API серіалізації для збереження їх на диску або для транспортування.

Оскільки дані в Інтернеті постійно збільшуються в геометричній прогресії, розрив між пам’яттю та диском стає все більшим.

Здебільшого самі дані не потрібно завантажувати в дорогу основну пам’ять. Тільки набагато важливіша інформація WHERE-A-DATA-IS заслуговує на місце в основній пам'яті.

Це те, що робить slim, зберігає якомога менше інформації в основній пам’яті, як мінімізований індекс величезної кількості зовнішніх даних.

SlimIndex: це загальна структура індексу, побудована на вершині SlimTrie .

SlimTrie - це основна структура даних індексу, розроблена з trie.

Особливості:

Зведено до мінімуму: 11 біт на ключ(набагато менше 64-бітового покажчика !).

Стабільний: споживання пам'яті стабільно в різних сценаріях. Найгірший випадок щільно сходиться до середнього споживання. Див. Еталон.

Loooong ключі: Ти можеш мати ДУЖЕ довгі клавіші (16 Кбайт), без витрат пам'яті (та грошей). Не витрачайте своє життя на написання чергового стиску префікса:). (aws-s3 обмежує довжину ключа 1024 байтами). Споживання пам'яті стосується лише кількості ключів, не до довжини ключа.

Впорядковано: як btree, ключі зберігаються. Діапазон-сканування буде готовий через 0.6.0 .

Швидко:

100 нс за Get (). Складність часу для отримання - O (log (n) + k); n: кількість ключів; k: довжина ключа .

Готовий до транспортування: один прото.Marshal () - це все, що потрібно для серіалізації, транспортування або збереження на диску тощо.

Слабко зчеплений дизайн: логіка індексу та зберігання даних повністю розділені. Шматок пирога за допомогою SlimTrie для індексації величезних даних.

Біти/ключ: пам'ять або дисковий простір у бітах ключ, споживаний в середньому. Він не змінюється, коли довжина ключа (k) стає більшою!

Час (у наносекундах), витрачений на Get () за допомогою golang-map, SlimTrie, array та btree від google.

  • В 3,3 рази швидше ніж btree.
  • В 2,3 рази швидше ніж двійковий пошук.