如何存储经常在DB中更改位置的有序物品 [英] How to store ordered items which often change position in DB
问题描述
我需要能够在DB中存储大量有序项目。到目前为止，这是直截了当的：
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 ...
...
在查询中，我总是需要得到一些项目（基于OtherFields进行过滤），但是顺序正确。
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".
现在问题：项目经常改变他们的位置，并且不仅仅是1或2.如果ID 2将位置从4736更改为2000，我需要更新其位置和位置之间的所有元素在旧位置2000和4735之间，每行添加1。而且每个交易不仅仅是一个ID变化，而且在短时间内可能会有很多交易。
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.
我认为最优雅的方式来处理 update 问题将使用链接列表而不是Position列，我可以通过将其前身连接到其后继者，然后将其插入到其新的前身和接班人。这将是每位职位更改的不变且少量更新，也将是我首选的处理更改的方式（在我的情况下为Java）。然而，这会以正确的顺序提高了查询的N + 1问题 - 即使对于几个元素，我必须在最坏的情况下查看整个列表以找出正确的顺序。
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:
-
是否有一个DBMS（理想的OpenSource）可以处理链接列出不仅与语法糖，而且具有良好的性能，例如通过使用链接元素的内部指数？
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?
也许这是一个选项，只需要一个BLOB，整个链接列表将被存储在！这样的链接列表可以在DB中使用多少内存，并且在获取的时候可以使用多达1000个条目？我正在使用Java + Hibernate来处理事情。我想象，在获取BLOB后，即使在内存中处理整个列表也应该很快！？
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!
推荐答案
如果放宽位置列必须包含从1到N的整数，而是允许它包含任何数字，那么您可以有效地进行搜索和更新。
If you relax the constraint that the Position column must contain integers from 1 to N and instead allow it to contain any numbers then you can do both searches and updates efficiently.
您可以在通过计算平均值（A + B）DIV 2，另外还有另外一个A，B位的项目。例如，如果A为10000，B为12000，那么您的新职位是11000.有时候你会因为聚集而耗尽空白，点可以穿过整个桌面，更均匀地重新分配位置。
You can insert an item between two other items with position A and B by calculating the average (A + B) DIV 2. For example if A is 10000 and B is 12000 then your new position is 11000. Occasionally you will run out of gaps due to clustering, at which point you can run through the whole table redistributing the positions more evenly.
这篇关于如何存储经常在DB中更改位置的有序物品的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
