Pau*_*lan 7 python database sorting django data-structures
我正在使用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中使用"REPEATABLE READ"级别的事务锁定是可能的.
我正在寻找更适合这种使用模式的备用数据结构.我已经看过这个问题了.
一个提议是Dewey十进制样式解决方案,它使插入操作在现有值之间以数字方式发生,因此在B和C之间插入A会导致:
A=1 -> B=2 B=2 -> A=2.5 C=3 -> C=3
这解决了列唯一性问题,但引入了列必须是指定小数位数的浮点数的问题.要么我高估了,要存储的数据超出了我的需要,要么系统受到我施加的任意小数长度的限制.此外,我不希望使用甚至超过数据库 - 一些密钥将比其他密钥更频繁地移动,使得该解决方案更快地达到极限.我可以通过定期重新编号数据库来解决这个问题,但似乎一个好的数据结构应该避免需要这个.
我考虑过的另一个结构是链表(和变体).这样做的优点是可以直接进行修改,但我不确定它的SQL属性 - 在SQL查询中排序这样的列表似乎很痛苦,并且提取列表的非顺序子集非常糟糕检索属性.
除此之外,还有B树,各种二叉树等等.你对这个数据结构有什么建议？SQL中的此解决方案是否有标准数据结构？使用顺序整数的最初想法是否真的会出现扩展问题,或者我发现哪些问题没有？
首选解决方案:
一个链表将是通常的方式来实现这一目标.在Oracle中,按顺序返回项目的查询是微不足道的,但我不确定如何在PostreSQL中执行此操作.
另一种选择是使用postgresql的ltree模块实现这一点.
不太优雅(并且写得很重)的解决方案: 启动事务.行级锁定范围内的"select for update".将目标记录移动到位置0,将目标未来的后续记录更新为+1,其位置高于目标原始位置(反之亦然),然后将目标更新到新位置 - 只需要一个额外的写入一个独特的约束.承诺:D
如果你可以等待Postgresql 8.5(Alpha可用),那么简单(但仍然写得很重)的解决方案:)
将其包装在事务中,选择范围内的更新,并使用延迟约束(postgresql 8.5支持延迟的唯一约束,如Oracle).