logoalt Hacker News

jlokier • today at 4:42 PM • 1 reply • view on HN

There's a general trick which combines the time complexities.

In the case of a sorted list, it's keeping a sorted list, along with a growing small unsorted list that you will query or sort when needed.

This works for kernel timer trees, database storage, and indexes.

Keep your "fixed" data up to some checkpoint in an efficient form, and your "new" data since the checkpoint in a faster-updating, slower-querying form. When doing queries, read both and merge, and maybe sort parts of the new data on demand. The new data will be slower to query, but it should also be smaller.

At carefully chosen times, transfer data from the new form to the "fixed" form, either with an incremental update if you can, or by rewriting the fixed form entirely. It doesn't have to stop at two layers, and shouldn't if the fixed form is large, or if you want unlimited scale.

Choosing the right times and how much to update (the whole key range, intervals, predicate subsets, ertc) is an interesting algorithm design problem. When you get it just right, you can get excellent performance in fast-queryable compression and continuous fast-updates at the same time. (I'm building a database engine that does this in my spare time.)


Replies