CODEWITHSUNDEEP
algorithmsortingdatabase-design
src091
src091

Reputation: 2847

Efficient and correct strategy for handling sortable items in a database

In a web application I have a set of entities in a database with a numeric field responsible for their ordering. On a client side these entities are displayed as a sortable list allowing users to change their order.

As of now I have two solutions for managing order updates and none of them satisfies me.

The first one is simple: every time user changes some item order, traverse updated list, get all items IDs into array, send it to a server and issue a series of updates where each item order is it's ID's index in array.
Drawbacks of this approach: lots of unnecessary updates, inability to correctly handle a situation when items array sent to a server does not contain all the entities IDs.

The second one is as follows: when user changes an item order, changed item's ID is sent to a server along with ID's of items that "surround" changed item in it's new place in list. On server item's new order is calculated by (previous.order + next.order) / 2. So if item with order 3 gets moved between items with orders 5 and 6, it's new order becomes 5.5
This solution requires only one update per change but also has a serious problem: due to the algorithm used every change increases the decimal part in order numbers and sooner or later it requires more precision then my database can provide (I use MongoDB for this case but I suppose it's not that important).

My question is if any other more efficient and correct ways exist or maybe my current approaches can be somehow improved?

Upvotes: 3

Views: 853

Answers (3)

Gerrat
Gerrat

Reputation: 29700

You could use a linked list in the database: Lose the order column, and store either the previous item ID or next item ID on that row.
Updates are trivial then (but extra work to display the list sorted).

Upvotes: 1

donkim
donkim

Reputation: 13137

I did something similar to your second approach. Instead of using doubles though, I used integers and spaced the items by 1000. This worked in my app for me, as the number of items wouldn't exceed 4M. Later, when I determine that the increment is now down to 1 (or something small), I would issue a reset command that would reset the intervals to be 1000 again. I did this using TSQL.

Hope this helps!

Upvotes: 2

Tom Anderson
Tom Anderson

Reputation: 47213

Describe the order in the database with an ordinal number, which starts at 0 for the first item and increases by 1 for every subsequent item. Then, you just need to send the ordinals of the moved item, and the ordinal of its new previous neighbour. You then do (i'm using $ to mark variables - you'll need to pass these into the queries from your code):

-- if $moved > $previous, and it's moving backwards, move everything between the new previous neighbour and the item forward one
update items
set ordinal = ordinal + 1
where ordinal > $previous
and ordinal < $moved;

-- else $moved < $previous, and it's moving forwards, move everything between the item and the new previous neighbour backwards one
update items
set ordinal = ordinal - 1
where ordinal > $moved
and ordinal <= $previous;

-- then move the item
update items
set ordinal = $previous + 1
where ordinal = $moved;

You could add a unique constraint to the ordinal column to help ensure integrity, but you'd have to be a bit cleverer about how you did updates.

Upvotes: 6

Related Questions