4 ms·

While implementing, I found that there is a large number of disk hops (and hence greater time required to read), and accessing data is slow. Only a chunk of dat

While implementing, I found that there is a large number of disk hops (and hence greater time required to read), and accessing data is slow. Only a chunk of data fits in a disk block (remember, there is a predefined size limit for blocks). How to get around this?

thesz 6y 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 6y ago
  Could you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.
  - JoeAltmaier 6y ago
    Interval-halving? Is that a thing with trees?
  - thesz 6y ago
    You 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

thesz 6y 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 6y ago
Could you elaborate on the "logarithmic method"? The fastest technique I know of to insert into sorted arrays uses a square-root decomposition.
- JoeAltmaier 6y ago
  Interval-halving? Is that a thing with trees?
- thesz 6y ago
  You 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