Today I got a task with one of those things™ again - allow users to order items in a list as they please with drag-and-drop UI.
I'd usually reach for integer :seq column and do a range update, it's performant enough for our needs and I don't need to worry about seq value drift, but today GPT convinced me that there might be a better approach - Fractional Indexing, specifically, it's Lexical variant where order values are strings, not integers (larger value-set, yay).
See https://github.com/sqliteai/fractional-indexing for reference.
The beauty of this approach is that it's O(1) - you only update the one item that changed place!
How it works
You define an alphabet, usually the ASCII-friendly base62 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz and when drag-and-dropping an item in a new position you provide :seq of both neighbours. Out of this we get three cases:
- Placed first, there is only right neighbor. Assume left to be 0 or 1 as needed.
- Placed in the middle, both neighbors present
- Placed last, only left neighbor present. Simply increment left neighbor's :seq by half of alphavet size (31)
In all cases the algo is similar. Convert the neighbor seq lexical values to integers and find the middle value between them. Convert this middle value back to lexical expression and set that as the new :seq of the record. Done.
Over time the :seq values will grow in length to cope with no values being available in gaps, but in practice values should not exceed 10 letters and getting this would require hundreds-to-thousands of tactical worst-case gap repositions.
Implementation tips
I'd recommend setting a value regex constraint on the column if you're using Postgres, so expected alphabet is enforced.
Top comments (0)