logoalt Hacker News

contravariant • today at 1:42 PM • 1 reply • view on HN

I think there's never going to be a point where you can have the kind of performance you can get by optimising a datastructure for a 'fixed' dataset. Nor can you get the maximal performance updating data if you need to maintain a useful datastructure.

A simple case is a sorted list, you can sort it after every update, you can ignore the ordering and sort it as needed, or you can use a datastructure that is typically O(log(N)) at both updates and retrieval. Better datastructurs help, but they cannot remove the tradeoff entirely (in fact O(log(N)) inserts are kind of theoretically minimal, though a trie can do it in O(1) for fixed length datatypes).


Replies

jlokier • today at 4:42 PM

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.)

➕ show 1 reply