[1] https://www3.cs.stonybrook.edu/~bender/newpub/BenderFaFi07.p...
Both structures exploit the fact that most of the data does not change much and can be packed as tight as one wishes. Even prefixes (and suffixes) can be factored out.
LSM allow for very compact data representation because most levels of the tree do not change much through time, and this is what we are talking about here. This compact representation makes LSM trees faster at sequential reads too (less pointer chasing).
Also, you can differently construct LSM trees for different operations: higher LSM tree with more narrow levels allows for faster writes, flatter LSM tree with less but wider levels allow for faster reads.
For example, if you represent a set of values as an ordered array, you can perform many set operations with the (array) merge algorithm, which is cache oblivious one. You can avoid pointer chasing, etc, but your structure becomes static instead of dynamic as with, say, red-black trees. This is already a win because you can save memory and compute if at least one of your sets does not change much.
But, if you apply logarithmic method [1] you can have dynamic data structure (over static one, a sorted array) and still perform most of operations without pointer chasing and with cache oblivious merging.
[1] https://www.scilit.com/publications/4dd8074c2d05ecc9ed96b5cf...
"Write-heavy" scenarios will probably be just fine with std::map (backed by an RB-tree) since the main downside of B-tree's is write amplification that isn't an issue since memory doesn't really have any block granularity.
LSM tree's in-memory will probably not be that useful as scanning becomes much more complicates (it's an interesting structure though if you have append-only workloads and want to implement dictionary for size-coded projects on top of a list).
B-trees algorithm requires leaf nodes to be filled up to some prespecified fill factor, usually from 50% to 70%. This is not compact by any measures.
Both LSM trees and COLA allow for much more compact storage. They also pretty cache friendly in the "cache oblivious" sense.
B-tree fill factors are a parameter that can be tuned to avoid extra splits depending on your insertion patterns, an in-memory variant doesn't need to be tuned like a disk-based variation.
Also nothing preventing the "bottom" of an LSM variation to be a dense B-tree like structure that just gets less updates.
The COLA paper also never mentions threading, an in-memory B-tree should scale better with size if there is multi-threading while I don't see an easy way to avoid big locks with COLA, maybe why the COLA paper was from 2000 and we haven't seen much additional development on it? (LSM-tree's work beautifully of course but then you basically have the double-space issue like with semi-space garbage collectors).
In the end, what you choose is dependent on your application and patterns, COLA is a clever structure that probably shines in some scenarios.
Like my scenario was a mostly heavy on consecutive insertions as well as lookups of potentially arbitrary compound keys, perfect for cola like since those are cheap.
> while I don't see an easy way to avoid big locks with COLA
Extension of COLA called Fractal Indexes (on-disk storage) are commercialized by Tokutek: https://en.wikipedia.org/wiki/Fractal_tree_index
You have to consolidate when the time has come to reclaim space and to avoid needless repeat compute during accesses. Might as well use it to run full LSM tactics. Especially when keeping in mind that array mapped trees have very simple index arithmetic once you treat them as semantically literally identical to a sorted (SoA) array with a cache-benefitting address/index scrambler.
No it wasn't; the C99 flexible array uses [] not [1] or [0].
When using the [1] hack, you cannot use the sizeof the structure to get the offset, because it includes the [1] array.
When using C99, you also cannot use sizeof to get the offset of the [0] element of the flexible array; sizeof is allowed to pretend that there is padding as if the flexible member were not there.
>
// The (N - 1) adjusts for the 1-element array in Payload struct
Payload *item = malloc(sizeof(Payload) + (N - 1) * sizeof(char))
If you are in C++ you need a cast; the void * return value of malloc cannot implicitly convert to Payload *.
Payload *item = static_cast<Payload *>(malloc(...));
Payload *item = (Payload *) malloc(...);
Payload *item = malloc(offsetof(Payload, elements) + N);
By taking the offset of the elements array, we don't need to subtract 1 from N to account for the [1] element being skipped by sizeof.
These kinds of little things take away complexity for something that must be carefully coded to avoid a memory safety issue. You really want the calculations around the memory to use the simplest possible formulas that are as easy as possible to reason about to convince yourself they are correct.
Also, when you do use sizeof in a malloc expression, the following pattern avoids repeating the type name for the size, and also lets a pair of parentheses be dropped since sizeof only requires parentheses when the operand is a type:
Payload *item = malloc(sizeof *item);No - strictly speaking, it does create objects. https://en.cppreference.com/w/cpp/memory/c/malloc.html#:~:te...
It gets confusing (to say the least) if you start questioning the details, but the spec does formally intend the objects to be implicitly created.
Payload *item = (Payload *)malloc(offsetof(Payload, elements[N]));
However, the traditional (and pretty much the only sensible) ways of defining offsetof do make it work.
N3220 draft:
offsetof(type, member-designator)
static type t;
This doesn't mean I won't use it, but just something to be aware of.
It might not be a bad idea to propose to ISO C that offsetof(type, array[n]) should be required to work, and for non-constant n too.
e.g., two B+ trees, one in RAM and one on disk, with the RAM one evicted with sieve caching? possibly a very lite WAL?
something that lets you use a B+ tree bigger than RAM, and persist to disk
https://www.youtube.com/playlist?list=PLSE8ODhjZXjYMAgsGH-Gt...
apelapan•4mo ago
whizzter•4mo ago
Eh yes, you're implementing your basic container, naturally a basic container won't cut it.
aidenn0•4mo ago
Obviously if you don't need (or only rarely need) in-order traversing (or related operations like successor), hash-tables are very fast.
If you do need in-order traversing, for small amounts of data, sorted arrays are very fast, and for large amounts of data various types of prefix-tries do very well.
apelapan•4mo ago
aidenn0•4mo ago
apelapan•4mo ago