用于高效修改的排序字段存储数据结构

7 投票

5 回答

6813 浏览

提问于 2025-04-15 15:28

我正在使用Django和PostgreSQL，但如果有更好的方法用原始SQL或数据库特定操作来实现，我并不一定非要用Django的ORM。

我有一个模型需要按顺序排列。查找操作通常会按顺序检索整个列表。对这些数据最常见的操作是将一行移动到列表的底部，同时让中间的一部分项目上浮，替换掉之前的项目，像这样：

(operation on A, with subset B, C, E)

A -> B
B -> C
C -> E
D -> D
E -> A

Notice how D does not move.

一般来说，中间的项目不会超过50个，但基础列表可能会增长到几万个条目。

实现这个功能最明显的方法是使用一个简单的整数顺序字段。但我觉得这样不太理想。这样做需要妥协，让位置排序的列变得不唯一，而不唯一性只在修改操作期间是必要的。为了理解这一点，想象一下使用A和子集B的最小操作：

oldpos = B.pos
B.pos = A.pos
A.pos = oldpos

即使你已经存储了位置，在第二行你也违反了唯一性约束。此外，这种方法让原子性变得麻烦——你的读取操作必须在写入之前进行，而在这段时间内你的记录可能会改变。Django默认的事务处理文档没有解决这个问题，尽管我知道在SQL中使用“可重复读”事务锁定级别应该是可行的。

我在寻找更适合这种使用模式的替代数据结构。我查看了这个问题以获取一些想法。

其中一个提议是使用杜威十进制式的解决方案，这样插入操作会在现有值之间按数字顺序进行，所以在B和C之间插入A会得到：

A=1   ->   B=2
B=2   ->   A=2.5
C=3   ->   C=3

这解决了列的唯一性问题，但引入了一个问题，即该列必须是一个指定小数位数的浮点数。要么我高估了，存储了比需要更多的数据，要么系统会受到我施加的任意小数长度的限制。此外，我不指望数据库的使用是均匀的——某些键会比其他键更频繁地移动，这使得这个解决方案更早达到限制。我可以通过定期重新编号数据库来解决这个问题，但我觉得一个好的数据结构应该避免需要这样做。

我考虑过的另一种结构是链表（及其变种）。这有一个优点，就是修改操作很简单，但我不确定它在SQL中的特性——在SQL查询中对这样的列表进行排序似乎会很麻烦，而提取一个非顺序的子集则会有很糟糕的检索性能。

除此之外，还有B树、各种二叉树等等。你推荐什么样的数据结构？在SQL中有没有标准的数据结构可以解决这个问题？最开始用顺序整数的想法真的会有扩展性问题，还是我在看到一些并不存在的问题？

数据结构浮点数排序算法数据库优化唯一性约束链表 B+树数据库事务

5 个回答

你可以通过将排序列设置为始终为偶数的整数来解决重新编号的问题。当你移动数据时，可以把排序字段改为新的排序值加1，然后快速更新一下，把所有奇数的排序字段转换为偶数：

update table set sort_order = bitand(sort_order, '0xFFFFFFFE')
where sort_order <> bitand(sort_order, '0xFFFFFFFE')

这样你就可以保持排序顺序的唯一性作为一个约束条件。

编辑：好的，再看看这个问题，我开始写一个新的回答。

回答于 2025-04-15 由 Python大师

分享举报

一个临时表和一个事务应该保持原子性，并且在排序顺序上要有唯一约束。简单来说，你想要从以下情况开始：

A  10   to  B  10
B  25       C  25
C  26       E  26
E  34       A  34

在每一行之间可以有任意数量的项目。所以，首先你需要读取记录并创建一个列表 [['A',10],['B',25],['C',26],['E',34]]。通过一些Python的魔法，你可以调整这些标识符，并把它们插入到一个临时表中：

create temporary table reorder (
    id varchar(20), -- whatever
    sort_order number,
    primary key (id));

现在进行更新：

update table XYZ
set sort_order = (select sort_order from reorder where xyz.id = reorder.id)
where id in (select id from reorder)

我只是猜测pgsql可以处理这个查询。如果可以的话，它将是原子的。

你可以选择创建一个名为REORDER的永久表，事务将确保尝试对同一记录进行两次重排序的操作是串行的。

编辑：这里有一些事务问题。你可能需要同时实现我提到的两个想法。如果两个进程都想更新项目B（例如），可能会出现问题。所以，假设所有的排序值都是偶数：

开始事务
将所有正在使用的排序值加1。这会在你要更新的所有行上加上行级写锁。
选择你刚刚更新的数据，如果有任何 sort_order 字段是偶数，说明其他进程已经添加了一个符合你条件的记录。你可以选择中止事务并重新开始，或者直接丢弃这个记录，完成操作，只使用在步骤2中更新的记录。选择“正确”的做法取决于你需要这段代码实现什么。
像上面那样使用正确的偶数排序值填充你的临时重排序表。
像上面那样更新主表。
删除临时表。
提交事务。

步骤2确保如果两个列表重叠，只有第一个列表会在事务完成之前访问到相关的行：

update XYZ set sort_order = sort_order + 1
where -- whatever your select criteria are

select * from XYZ
where -- same select criteria
order by sort_order

另外，你可以在表中添加一个控制字段来达到相同的效果，这样就不需要处理 sort_order 字段。使用 sort_order 字段的好处是，通常情况下，按BIT字段或 LOCK_BY_USERID 字段进行索引的性能较差，因为这个字段99%的时间都是空的。SQL引擎不喜欢那些大部分时间都是空的索引。

回答于 2025-04-15 由 Python大师

分享举报

推荐的解决方案：

通常情况下，使用链表是实现这个功能的常见方法。在Oracle中，想要按顺序返回项目的查询是非常简单的，但我不太确定在PostgreSQL中该怎么做。

另一个选择是使用PostgreSQL的ltree模块来实现。

不太优雅（而且写入操作较多）的解决方案：
开始一个事务。在范围内使用“select for update”来进行行级锁定。将目标记录移动到位置0，然后更新目标之后的记录，将它们的位置加1（如果它们的位置高于目标的原始位置），然后再将目标更新为新的位置——这样就比没有唯一约束时多写了一次。最后提交 :D

简单（但仍然写入操作较多）的解决方案，如果你能等到PostgreSQL 8.5（目前有Alpha版本可用） :)
将其放在一个事务中，在范围内使用select for update，并使用延迟约束（PostgreSQL 8.5支持延迟唯一约束，就像Oracle一样）。

回答于 2025-04-15 由 Python大师

分享举报

用于高效修改的排序字段存储数据结构

5 个回答

撰写回答