Log-Structured Merge-Tree
E717514
A Log-Structured Merge-Tree (LSM-tree) is a write-optimized data structure that organizes data in sequential logs and periodically merges them to provide efficient writes and good read performance for key-value storage systems.
All labels observed (4)
| Label | Occurrences |
|---|---|
| LSM-tree | 1 |
| Log-Structured Merge-Tree canonical | 1 |
| The Log-Structured Merge-Tree (LSM-Tree) paper | 1 |
| log-structured merge tree | 1 |
How this entity was disambiguated
This entity first appeared as the object of triple T8151863 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.
NED1
Entity disambiguation (via context triple)
gpt-5-mini-2025-08-07
Target entity: Log-Structured Merge-Tree Context triple: [RocksDB, usesArchitecture, Log-Structured Merge-Tree]
-
A.
LSM
LSM is an undergraduate dual-degree program at the University of Pennsylvania that integrates rigorous training in life sciences with business and management education.
-
B.
Raft consensus algorithm
Raft consensus algorithm is a distributed consensus protocol designed to be more understandable and easier to implement than Paxos while providing equivalent fault-tolerant guarantees.
-
C.
B-tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
-
D.
RocksDB
RocksDB is a high-performance, embeddable key–value store developed by Facebook, optimized for fast storage on flash and solid-state drives using a Log-Structured Merge-Tree (LSM) architecture.
-
E.
Paxos consensus algorithm
The Paxos consensus algorithm is a fault-tolerant protocol for achieving agreement among distributed systems, widely used as a foundation for reliable, replicated state machines and modern distributed databases.
- F. None of above. chosen
- G. Unsure - the case is ambiguous/there is not enough information to decide.
NED2
Entity disambiguation (via description)
gpt-5-mini-2025-08-07
Target entity: Log-Structured Merge-Tree Target entity description: A Log-Structured Merge-Tree (LSM-tree) is a write-optimized data structure that organizes data in sequential logs and periodically merges them to provide efficient writes and good read performance for key-value storage systems.
-
A.
LSM
LSM is an undergraduate dual-degree program at the University of Pennsylvania that integrates rigorous training in life sciences with business and management education.
-
B.
Raft consensus algorithm
Raft consensus algorithm is a distributed consensus protocol designed to be more understandable and easier to implement than Paxos while providing equivalent fault-tolerant guarantees.
-
C.
B-tree
A B-tree is a self-balancing tree data structure that maintains sorted data and allows efficient insertion, deletion, and search operations, commonly used to implement database indexes.
-
D.
RocksDB
RocksDB is a high-performance, embeddable key–value store developed by Facebook, optimized for fast storage on flash and solid-state drives using a Log-Structured Merge-Tree (LSM) architecture.
-
E.
Paxos consensus algorithm
The Paxos consensus algorithm is a fault-tolerant protocol for achieving agreement among distributed systems, widely used as a foundation for reliable, replicated state machines and modern distributed databases.
- F. None of above. chosen
Statements (71)
| Predicate | Object |
|---|---|
| instanceOf |
data structure
ⓘ
index structure ⓘ write-optimized data structure ⓘ |
| advantageOverBTree | better performance on write-heavy workloads ⓘ |
| contrastedWith |
B+ tree
ⓘ
B-tree ⓘ |
| describedIn |
The Log-Structured Merge-Tree (LSM-Tree) paper
ⓘ
linked to:
Log-Structured Merge-Tree
|
| disadvantageComparedToBTree |
higher read amplification
ⓘ
higher space amplification ⓘ |
| hasAcronym |
LSM-tree
ⓘ
linked to:
Log-Structured Merge-Tree
|
| hasComponent |
SSTable
ⓘ
linked to:
SSTables
compaction process ⓘ immutable memtable ⓘ memtable ⓘ multiple levels ⓘ sorted run ⓘ write-ahead log ⓘ |
| hasConcept |
hybrid compaction
ⓘ
leveling compaction ⓘ tiering compaction ⓘ |
| hasGoal |
efficient storage utilization
ⓘ
efficient writes ⓘ good read performance ⓘ |
| hasOperation |
compaction between levels
ⓘ
flush from memory to disk ⓘ merge of sorted runs ⓘ |
| hasProperty |
append-friendly
ⓘ
log-structured ⓘ merge-based ⓘ multi-level ⓘ sequential-write-oriented ⓘ supports compaction ⓘ supports high write throughput ⓘ supports point lookups ⓘ supports range queries ⓘ write-optimized ⓘ |
| introducedBy |
Dieter Gawlick
ⓘ
Edward Cheng ⓘ Elizabeth O’Neil ⓘ Patrick O’Neil ⓘ |
| introducedIn | 1996 ⓘ |
| mitigatedBy |
Bloom filters
ⓘ
caching ⓘ careful compaction policies ⓘ |
| optimizesFor |
high write throughput
ⓘ
sequential disk writes ⓘ |
| organizesDataAs |
sequential logs
ⓘ
sorted runs on disk ⓘ |
| performs |
background compaction
ⓘ
periodic merges ⓘ |
| stores | key-value pairs ⓘ |
| supports |
deletions via tombstones
ⓘ
ordered iteration ⓘ range scans ⓘ upserts ⓘ |
| tradesOff |
read amplification
ⓘ
space amplification ⓘ write amplification ⓘ |
| usedFor |
NoSQL databases
ⓘ
key-value storage systems ⓘ log-structured file systems ⓘ log-structured storage ⓘ persistent key-value stores ⓘ write-intensive workloads ⓘ |
| usedIn |
Cassandra
ⓘ
HBase ⓘ
linked to:
Apache HBase
LevelDB ⓘ RocksDB ⓘ ScyllaDB ⓘ WiredTiger storage engine ⓘ
linked to:
WiredTiger
many modern NoSQL systems ⓘ |
How these facts were elicited
The pipeline generated the facts above by prompting gpt-5.1 with this entity's name + description and the instruction below.
Instruction
You are a knowledge base construction expert. Given a subject entity and a description of it, return factual statements that you know for the subject as a JSON list of dictionaries(triples), where keys must be "subject", "predicate" and "object". The number of facts may be very high, between 25 to 50 or more, for very popular subjects. For less popular subjects, the number of facts can be very low, like 5 or 10. # Requirements - If you don't know the subject at all, return an empty list. - If the subject is not a named entity, return an empty list. - Include at least one triple where predicate is "instanceOf". - Do not get too wordy. - Separate several objects into multiple triples with one object.
Input
Subject: Log-Structured Merge-Tree Description of subject: A Log-Structured Merge-Tree (LSM-tree) is a write-optimized data structure that organizes data in sequential logs and periodically merges them to provide efficient writes and good read performance for key-value storage systems.
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
linked to: Log-Structured Merge-Tree
linked to: Log-Structured Merge-Tree
linked to: Log-Structured Merge-Tree