7 ms·
B+-trees degrade quite fast with the slightest hint of randomness in the inserted data. To get around this unfortunate property people invented Log-structured
by thesz 7y ago
B+-trees degrade quite fast with the slightest hint of randomness in the inserted data.
To get around this unfortunate property people invented Log-structured Merge Trees - you keep new part of your data which is easy to insert randomly to and once in a while merge it (as sorted data!) with main data. This way degradation is greatly reduced at the expense of reading speed in case of merge.
BTW, LTMs are a variant of the logarithmic method - a way to create dynamic structures (fast to insert and query) from static ones (slow to insert, fast to query). Even sorted arrays can be made fast for insertion in this way.
Anyway, try to keep your insertion order as sorted as possible. Delay actual insertion into disk data if needed.
- senderista 7y agoCould you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.
- JoeAltmaier 7y agoInterval-halving? Is that a thing with trees?
- thesz 7y agoYou can split a collection of 2^(k-1)<=N<2^k elements into up to k arrays with length 2^i. Insertion into empty array with one element capacity is easy, insertion into array with single element creates an array with two elements. If you already have an array of two elements, you should merge these elements into array of 4 elements. The merge operation is fast and cache oblivious. Thus, insertion into a set of these arrays is fast. Query is not so fast - O(log^2N). But I can direct you to Cache-Oblivious Lookahead Arrays (COLA) paper where a technique to get back to O(logN) complexity for lookup is described. Or you can simple merge these arrays into one at the bulk insertion end. Source code (not mine): https://github.com/giannitedesco/cola https://github.com/giannitedesco/cola