LexSortKey

Lexicographically sortable keys for ordered sequences in Elixir.

This library implements fractional indexing as outlined in:

Use Cases

Real-time collaborative editing (like Figma, Notion, Linear)
Ordered lists in databases without reindexing
Distributed systems where clients generate keys independently
Any scenario requiring insertion at arbitrary positions

Installation

Add lex_sort_key to your list of dependencies in mix.exs:

def deps do
  [
    {:lex_sort_key, "~> 0.1.0"}
  ]
end

Quick Start

# Create initial keys for a list
keys = LexSortKey.n_first(3)
# => ["a0", "a1", "a2"]

# Insert between two keys
{:ok, between} = LexSortKey.between("a0", "a1")
# => {:ok, "a0V"}

# Keys sort correctly as strings
Enum.sort(["a1", "a0V", "a0"])
# => ["a0", "a0V", "a1"]

How It Works

Keys consist of two parts: a variable-length integer and an optional fractional part.

Variable-Length Integer Encoding

The first character determines the length, enabling correct lexicographic sorting:

Prefix	Length	Range	Example
`Z`	2 chars	62 values	`Z0` to `Zz`
`a`	2 chars	62 values	`a0` to `az`
`b`	3 chars	3,844 values	`b00` to `bzz`
`c`	4 chars	238,328 values	`c000` to `czzz`

Uppercase letters (A-Z) represent values before a0, lowercase (a-z) represent values after.

Fractional Part

When inserting between adjacent integers, a fractional part is appended:

LexSortKey.between("a0", "a1")    # => "a0V"
LexSortKey.between("a0", "a0V")   # => "a0F"
LexSortKey.between("a0V", "a1")   # => "a0k"

API Reference

Basic Operations

# Get the first key (zero key)
LexSortKey.first()
# => "a0"

# Generate key after another
{:ok, key} = LexSortKey.key_after("a0")
# => {:ok, "a1"}

# Generate key before another
{:ok, key} = LexSortKey.key_before("a1")
# => {:ok, "a0"}

# Generate key between two keys
{:ok, key} = LexSortKey.between("a0", "a1")
# => {:ok, "a0V"}

Bulk Operations

# Generate N consecutive keys starting from a0
LexSortKey.n_first(5)
# => ["a0", "a1", "a2", "a3", "a4"]

# Generate N keys after a given key
{:ok, keys} = LexSortKey.n_after("a0", 3)
# => {:ok, ["a1", "a2", "a3"]}

# Generate N keys before a given key
{:ok, keys} = LexSortKey.n_before("a2", 2)
# => {:ok, ["a0", "a0V"]}

# Generate N keys between two keys
{:ok, keys} = LexSortKey.n_between("a0", "a1", 3)
# => {:ok, ["a0V", "a0k", "a0s"]}

# Distributed insertion (shorter keys)
{:ok, keys} = LexSortKey.n_between_distributed("a0", "a1", 3)
# => {:ok, ["a0F", "a0V", "a0k"]}

# Efficient prepending
{:ok, keys} = LexSortKey.prepend_n("a0", 3)
# => {:ok, ["Zx", "Zy", "Zz"]}

Rebalancing

After many insertions, keys can grow long. Rebalance to get compact keys:

# Long keys from repeated insertions
long_keys = ["a0", "a0VVVVVV", "a0VVVVVk", "a1"]

# Rebalance to short keys
{:ok, short_keys} = LexSortKey.rebalance(long_keys)
# => {:ok, ["a0", "a1", "a2", "a3"]}

# Rebalance with bounds (preserves surrounding keys)
{:ok, keys} = LexSortKey.rebalance(keys, lower_bound: "a0", upper_bound: "b00")

# Rebalance only a portion of the list
{:ok, keys} = LexSortKey.rebalance_range(keys, 1..3)

Performance Considerations

Sequential insertions best case: Inserting on first or last position keeps the keys sweet and short. 1M keys is 5 chars and takes few usec per key to generate.
Sequential insertions worst case: But in worst case scenario keys can grow logarithmically. After 1000 sequential inserts on a second position, max key length is ~169 characters.
Distributed insertions: Using n_between_distributed/3 keeps keys much shorter (~4 characters for 1000 keys).
Rebalancing: Call rebalance/1 periodically to reset key lengths to optimal (~2-3 characters).

iex()> Enum.reduce(1..1000, nil, fn _, acc -> LexSortKey.key_before(acc) |> elem(1)  end) |> IO.puts
Ykt
iex()> Enum.reduce(1..1000, nil, fn _, acc -> LexSortKey.key_after(acc) |> elem(1)  end) |> IO.puts
bF7
iex()> Enum.reduce(1..1000, nil, fn _, acc -> LexSortKey.between("a0", acc) |> elem(1)  end) |> IO.puts
a000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
:timer.tc(fn -> Enum.reduce(1..1000000, nil, fn _, acc -> LexSortKey.key_after(acc) |> elem(1)  end) end)
{3345962, "d3B81"}

License

MIT License. See LICENSE for details.