如何存储经常改变数据库中位置的订购项目 [英] How to store ordered items which often change position in 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 ...
...
在查询中，我总是只需要按正确的顺序获取几个项目(根据其他字段过滤).也很简单，在位置上放置一个索引并使用按位置排序".
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.
我认为处理更新问题的最优雅的方法是使用链接列表而不是位置列，我可以通过将其前任链接到其后继者来将 ID 2 从其旧位置删除然后通过将其链接到新的前任和继任者之间，将其插入到别处.这将是每次位置更改的恒定且少量的更新，这也是我处理更改的首选方式(在我的情况下是 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(理想情况下是开源的)不仅可以使用语法糖处理链表，而且还具有良好的性能，例如通过对链接元素使用内部索引?
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 来存储整个链表也是一种选择！这样的链表可以有多大/它在数据库中使用多少内存以及在获取时假设 1.000.000 个条目?我正在使用 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!?
当然也欢迎其他想法！
推荐答案
如果您放宽限制 Position 列必须包含从 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.
这篇关于如何存储经常改变数据库中位置的订购项目的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
