Описание тега lsm-tree
In computer science, the Log-Structured Merge-Tree (or LSM-tree) is a data structure with performance characteristics that make it attractive for providing indexed access to files with high insert volume, such as transactional log data.
2
ответа
LSM Tree время поиска
Какова наихудшая временная сложность в дереве слияния с лог-структурой для простого поискового запроса (например, запроса одного WHERE пункт)? Это O(журнал N)? O(N*Log N)? Что-то другое? Как насчет нескольких запросов, таких как поиск нескольких WHE…
11 авг '13 в 00:27
0
ответов
Более быстрый способ очистить семейство столбцов в rocksdb
Я ищу способы быстрее очистить данные семейства столбцов в rocksdb без значительных накладных расходов (включая уплотнение). Мне нужно очистить семейство столбцов как один раз для каждых 5К строк (которые вставляются с помощью ряда вызовов write_bat…
30 янв '19 в 10:49
1
ответ
Почему фильтры Блума не могут обрабатывать запросы диапазона?
Контекст: я читаю о деревьях RocksDB и LSM, насколько я понимаю, фильтр Bloom используется, чтобы избежать множественных операций ввода-вывода для извлечения элементов на всех уровнях хранения. И я в порядке с этим. Очевидно, одна из проблем заключа…
03 июл '18 в 11:38
0
ответов
Уплотнение не запускается в породе
У меня проблемы с запуском сжатий во время массовой вставки с использованием HASHSKIPLIST memtable в rocksdb. Я использую формат файла PlainTable SST. Размер Memtable установлен равным 64 МБ, а количество буферов записи равно 6. При вставке 200 милл…
28 дек '17 в 06:58
1
ответ
Использование дерева LSM, такого как LevelDB, в качестве механизма хранения для RDBMS
Дерево LSM было успешно использовано во многих механизмах no-sql, его данные сортируются по ключам, а не по хеш-таблицам, что позволяет использовать их много за пределами хранилища kv. Например, база данных временных рядов (TSDB) может хорошо подход…
03 авг '16 в 01:04
1
ответ
Почему LevelDB делает свой нижний уровень в 10 раз больше верхнего?
Согласно официальному документу, нет никаких сомнений в том, что нижний уровень в 10 раз больше верхнего уровня в LevelDB. Вопрос в том, почему 10? не 2? не 20? Это связано с какими-то строгими математическими вычислениями или это просто работает? Я…
15 сен '18 в 15:47
1
ответ
Как запросы диапазона работают в LSM (дерево слияния структуры журнала)?
Недавно я изучал общие структуры индексации в базах данных, такие как B+-деревья и LSM. У меня есть твердое представление о том, как точка чтения / записи / удаления / сжатия будет работать в LSM. Например (в RocksDB/levelDB) при чтении точечного за…
09 янв '19 в 22:18
1
ответ
Использует ли BigTable уплотнение Tiered или Leveled LSM-tree?
Google BigTable - это система, которая использует LSM-дерево в качестве основной структуры данных для хранения. LSM-дерево может использовать разные стратегии слияния. Двумя наиболее распространенными являются (1) уровневое объединение, которое боле…
22 янв '19 в 16:59
1
ответ
Как пропустить некоторые ключи с помощью итератора?
В качестве примера, я добавил несколько ключей в БД, например, <1 + 2> <1 + 3> <2 + 1> <2 + 4> <3 + 2> Первый, Seek() до <1, 2>, а затем Next() на <1, 3>После этого я хочу пропустить клавиши <2, 1> и <2, 4> (чей префикс…
06 июн '19 в 15:45
4
ответа
В чем разница между терминами SSTable и LSM Tree
Используются ли эти два термина как взаимозаменяемые? Я читал о том, как работает SSTable, и обычно в статьях просто упоминается LSM Tree. Однако, похоже, это одно и то же. Когда я должен использовать один термин вместо другого?
30 сен '19 в 16:21
1
ответ
MongoDB: Как я могу изменить тип движка (с B-Tree на LSM-Tree) индекса _id_?
Мы можем создать коллекцию с помощью движка WiredTiger и type=lsm, но эта функция не упоминается в документах MongoDB: db.createCollection( "test", { storageEngine: { wiredTiger: {configString: "type=lsm"}}} ) После вставки нескольких документов и д…
15 янв '20 в 15:11
0
ответов
Как работать с ключами разной длины в SSTable?
Я пытаюсь реализовать постоянный инвертированный индекс на диске. Я решил использовать структуру, подобную Sorted-String-Table, чтобы сохранить ее в файл, где ключи хранятся в отсортированном порядке. Но как поступить, если ключи могут иметь разную …
29 июн '20 в 14:56
1
ответ
Как HBase выполняет обновления со скоростью передачи данных по диску, а не со скоростью поиска по диску?
Я читаю книгу HBase: The Definitive Guide, и там упоминается, что, хотя традиционные реляционные базы данных выполняют обновления / удаления со скоростью поиска (B-деревья), HBase выполняет обновления / удаления со скоростью передачи (деревья LSM). …
20 янв '20 в 17:10
1
ответ
Как сохранить разреженный индекс в LSM-дереве?
В разделе «Разработка приложений с интенсивным использованием данных» Мартин вводит структуру данных, называемую LSM-деревьями. В основном это 3 части: таблица памяти в памяти (обычно красно-черное дерево), разреженный индекс в памяти и SSTables на …
08 сен '21 в 15:58
0
ответов
Является ли дублированный ключ законной проблемой при сканировании базы данных KV на основе LSM-дерева?
Привет, я узнал, что один ключ может отображаться более одного раза в базе данных на основе LSM-дерева. Это связано с тем, что ключ записывается на диск путем добавления вместо перезаписи. Я понимаю, что если мы хотим прочитать значение ключа, мы мо…
21 май '22 в 01:40
0
ответов
Понимание того, как реализация Disk-Storage агента открытой политики (OPA) использует файлы .sst и .vlog (BadgerDB)
Я работаю с некоторыми примерами OPA , подобными этому , которые используют дисковое хранилище. Я удалил временный каталог в пользу постоянного (как в производственной системе) и заметил странное поведение. Если я сначала напишу пример записи "authz…
19 апр '22 в 15:26
2
ответа
Как именно memtable сбрасывается в SSTable на диске в LSM-деревьях?
С точки зрения реализации, как именно memtable (в Cassandra, RocksDB, LevelDB или любом LSM-дереве) сбрасывается в SSTable? Я понимаю, что memtable представляет собой отсортированные данные, структурированные, как красно-черное дерево, но как нам пр…
04 авг '22 в 03:54
0
ответов
Как MongoDB WiredTiger хранит файлы
MongoDB WiredTiger предлагает LSMT для хранения. Отлично, поэтому в памяти поддерживается сбалансированное дерево поиска, которое сбрасывается на диск в зависимости от конфигурации (времени или размера). Но вопрос в том, как данные хранятся на диске…
27 окт '22 в 19:03
0
ответов
Балансировка доступа к хранилищу ключей и значений LSM между пользователями и проблема «зависания»
Типичные базы данных LSM «ключ-значение», такие как goleveldb, имеют непредсказуемую пропускную способность. Они могут записать большой пакет данных в L0, но затем «застрять», пока не будут завершены все так называемые «сжатия». В моем приложении до…
25 окт '23 в 09:08