How to store ordered items which often change position in DB

user_360480 0
Viewed 5511

I need to be able to store a large list of ordered items in the DB. So far that's straight-forward:

ID Position OtherFields
 1     45      ...
 2   4736      ...
 3    514      ...
 ...

In queries, I always need to get just a few items (filtered based on OtherFields) but in the correct order. Easy as well, putting an index on Position and using "order by Position".

Now the problem: Items change their Position frequently, and not just by 1 or 2. If ID 2 changes the Position from 4736 to 2000, I need to update its Position and the Position of all elements between old Position 2000 and 4735, adding 1 in each row. And it's not only one ID that changes per transaction but a few, and there can be many transactions within a short time.

I think the most elegant way to handle the update problem would be using a linked list instead of a Position column where I can just remove ID 2 from its old position by linking its predecessor to its successor and then insert it elsewhere by linking it between its new predecessor and successor. That would be a constant and small number of updates per Position change and it would also be my preferred way of handling the changes (in Java in my case). However this raises the N+1 problem for querying in the correct order - even for a few elements, I have to go through the whole list in the worst case for finding out their correct order.

So my question is: What would you recommend to get a good balance between necessary updates and query performance?

So far I see two promising directions:

  1. Is there a DBMS (ideally OpenSource) that can handle linked lists not only with syntactic sugar but also with a good performance, e.g. by using internal Indices for the linked elements?

  2. Maybe it would also be an option to just have a BLOB where the whole Linked List would be stored in! How big could such a Linked List get / how much memory would it use in the DB and when fetched for let's say 1.000.000 entries? I'm using Java + Hibernate in case it matters. I imagine that processing even the whole list in memory after fetching the BLOB should be pretty fast!?

But of course other ideas are welcome as well!

recursion data-structures linked-list indexing sql
4 Answers

Another solution would be to use lexical ranking. Whenever there is no value between two strings, one would simply add a new character. The only disadvantage is, that it consumes more memory compared to a numerical solution, which are named in other answers.

A normalization isn't necessary for an error free database, but can be optionally done to reduce the string lenght.

Here is an interesting video, which explains it in detail: https://www.youtube.com/watch?v=OjQv9xMoFbg&feature=youtu.be

user_44541570
Related