Show HN: An embeddable fractional indexing library in C(github.com)

3 pointsby marcobambinia day ago2 comments

miki_shipsa day ago
Fractional indexing is one of those ideas that looks obvious until you run it in a long-lived list and the keys start growing weirdly. Curious how you handle that tradeoff here. Do you rebalance or renumber at some point, or is compaction left to the caller?
- marcobambinia day ago
  Good question, in the current version, compaction is left to the caller.
  The library does a few things to keep key growth practical:
  1. generate_n_keys_between: if you know you're inserting N items at once (e.g. a bulk paste or drag of multiple items), it distributes them evenly in a single call rather than chaining N sequential generate_key_between calls, which would produce progressively longer keys. 2. Higher bases: base62 (default) and base95 give you a much wider branching factor per character than base10, so keys stay shorter under the same insertion patterns.
  But yes, in a long-lived list with adversarial insertion patterns (always inserting at the same spot), keys will grow unboundedly, that's inherent to the algorithm. In practice, compaction is an application-level concern: you'd pick a quiet moment (or a sync boundary, if you're doing CRDT-style collaboration) and renumber the whole list with fresh, evenly spaced keys.
  The library gives you generate_n_keys_between(NULL, NULL, n) which makes trivial to generate N fresh keys for the whole list in one call.
  - miki_ships20 hours ago
    The sync boundary framing makes sense. Do you expose any way to detect when compaction is worth triggering -- key length threshold, some depth metric -- or is that left entirely to the caller to figure out empirically?
    marcobambini10 hours ago
    No, the library is intentionally minimal on that front. It generates and validates keys but doesn't track any metadata about them. Keys are plain C strings, so detecting "time to compact" is straightforward on the caller's side:
    - Key length is the most natural signal, just strlen(). If your base62 keys are typically 3-5 characters and you start seeing 15+, that's a reasonable trigger. - Max key length in the list is cheap to track if you're already iterating for display or sync.
    Keeping that policy out of the library is intentional. What counts as "too long" depends entirely on the application. A SQLite column with a B-tree index cares about different thresholds than an in-memory CRDT. And the right moment to compact (sync boundary, idle tick, batch write) is an app-level scheduling decision the library has no business making.
zenon_paradoxa day ago
[flagged]