数据库中有序列表的最佳表示形式？

我知道这有点违背关系数据库的原则，但让我来描述一下情况。

我有一个页面，用户将放置一些项目。

 ________________
| -Item1         |
| -Item2         |
| -Item3         |
| -Item4         |
|________________|

这些项目必须按照用户给它们的顺序保持。但是这个顺序可以被用户改变任意次数。

 ________________
| -Item1         |
| -Item4         |
| -Item2         |
| -Item3         |
|________________|

进场1

我最初的想法是给这些项目一个索引来表示它们在列表中的位置

Page           Item
-----------    ---------------
FK | pid       FK | pid
| name      PK | iid
| index
| content

有了这个解决方案，您可以选择项目 where pid = Page.pid和 order by index，这是方便的。然而，每次你改变顺序，你必须改变其他项目(最好的情况)和所有其他项目(最坏的情况)之间的任何地方。

进场二

我还考虑过创建一个类似于数据结构的“链表”，其中每个项目都指向列表中的下一个项目。

Page           Item
-----------    ---------------
FK | pid       FK | pid
| name      PK | iid
| next
| content

这可能会降低更改订单的成本，但是我们必须依靠前端编程来提取订单。

有我没想到的方法吗? 请告诉我。

25210 次浏览
小开

您可以向 Page表中添加一个名为 order的新字符(nvarchar)列，它包含按照您喜欢的顺序(即 1,4,3,2)分隔的 iid列表。优点是只需要维护一个表中的一个字段——明显的缺点是需要编写一个实用函数来在字符和数字类型之间进行转换，而实际上这可能不会花费太长时间。

小开

如果您期望的项目数量不是很大，那么您可以使用第一种方法的稍微修改的版本。在连续的索引之间拉开距离。例如，第一个项目有索引100，第二个项目有索引200，等等。这样，您就不必每次都更新所有索引，只有在找不到空白的情况下才需要这样做

小开

使用 进场1并处理索引更新的性能影响。除非您处理的是每页的 几百万项，否则不太可能发现缺乏的性能，并且您保留了 SQL 处理 设置数据的所有能力。

除了在纯非过程 SQL 中更难处理之外，进场二还需要您遍历列表，以便在重新排序项目时找到重新连接“链接”的合适位置。

小开
最佳答案

我认为@a1ex07在这方面是正确的(+ 1)。我不认为 itemOrder中的差距违反了3NF，但我确实担心另一种违反3NF 的情况(更多关于这一点)。我们还必须注意 itemOrder领域的错误数据。我是这样开始的:

create table pages (
pid int,
primary key (pid)
);


create table users (
uid int,
primary key (uid)
);


create table items (
iid int,
primary key (iid)
);


create table details (
pid int not null references pages(pid),
uid int not null references users(uid),
iid int not null references items(iid),
itemOrder int,
primary key (pid, uid, iid),
unique (pid, uid, itemOrder)
);

主键确保对于每个页面，对于每个用户，都有唯一的项。唯一约束确保对于每个页面，对于每个用户，都有唯一的 itemOrders。下面是我对3NF 的担心: 在这个场景中，itemOrder并不完全依赖于主键; 它只依赖于 (pid, uid)部分。这还不到2NF 这是个问题。我们可以在主键中包含 itemOrder，但是我担心它可能不是最小的，因为 PK 需要如此。我们可能需要把它分解成更多的表。还在想..。

[编辑: 更多关于这个话题的思考... ... ]

假设

  1. 有用户。

  2. 有好几页。

  3. 有些东西。

  4. (页面，用户)标识一组项目。

  5. (page，user)标识一个有序的插槽列表，如果需要，我们可以在其中存储项目。

  6. 我们不希望在(页面，用户)的列表中有重复的项目。

A 计划

关闭上面的 details表。

添加一个表 ItemsByPageAndUser，以表示由(页面、用户)标识的项的 SET。

create table ItemsByPageAndUser (
pid int not null references pages(pid),
uid int not null references users(uid),
iid int not null references items(iid),
primary key (pid, uid, iid)
)

添加表 SlotsByPageAndUser，以表示可能包含项的插槽的有序列表。

create table SlotsByPageAndUser (
pid       int not null references pages(pid),
uid       int not null references users(uid),
slotNum   int not null,
iidInSlot int          references items(iid),
primary key (pid, uid, slotNum),
foreign key (pid, uid, iid) references ItemsByPageAndUser(pid, uid, iid),
unique (pid, uid, iid)
)

注意1 : iidInSlot是可以为空的，所以如果我们想要的话，我们可以有空的插槽。但是，如果有一个项目出现，它必须根据项目表进行检查。

注意2 : 我们需要最后一个 FK 来确保我们不添加任何不在这个(用户，页面)可能项目集中的项目。

注3 : 对 (pid, uid, iid)的独特约束强化了我们的设计目标，即在列表中拥有独特的项目(假设6)。如果没有这些，我们可以从由(页面，用户)标识的集合中添加任意数量的条目，只要它们位于不同的插槽中。

现在我们已经很好地解耦了项与它们的槽，同时保留了它们对(页面、用户)的公共依赖性。

这个设计当然是在3NF 和可能是在 BCNF，虽然我担心 SlotsByPageAndUser在这方面。

问题是，由于表 SlotsByPageAndUser中的唯一约束，SlotsByPageAndUser和 ItemsByPageAndUser之间的关系基数是一对一的。通常，不是实体子类型的1-1关系是错误的。当然，也有例外，也许这就是其中之一。但也许还有更好的办法。

B 计划

  1. 关闭 SlotsByPageAndUser表。

  2. 将 slotNum列添加到 ItemsByPageAndUser。

  3. 将 (pid, uid, iid)上的唯一约束添加到 ItemsByPageAndUser。

现在是:

create table ItemsByPageAndUser (
pid     int not null references pages(pid),
uid     int not null references users(uid),
iid     int not null references items(iid),
slotNum int,
primary key (pid, uid, iid),
unique (pid, uid, slotNum)
)

注意4 : 保留 slotNum为空可以保留我们指定集合中不在列表中的项的能力。但是..。

注意5 : 对涉及可空列的表达式施加唯一约束可能会在某些数据库中导致“有趣的”结果。我认为在 Postgres 会如我们所愿。(请参阅这里的 这个讨论。)对于其他数据库，里程可能会有所不同。

现在没有混乱的1-1关系挂在周围，所以这是更好的。 它仍然是3NF，因为唯一的非键属性(slotNum)依赖于键、整个键，除了键以外什么都不依赖。(你不能问关于 slotNum没有告诉我什么页面，用户，和项目你正在谈论。)

它不是 BCNF，因为[ (pid, uid, iid)-> slotNum]和[ (pid,uid,slotNum)-> iid]。但是这就是为什么我们对(pid、 uid、 slotNum)有唯一的约束，它可以防止数据进入不一致的状态。

我认为这是一个可行的解决方案。

小开

解决方案: 使 index成为一个字符串(因为字符串本质上具有无限的“任意精度”)。或者，如果使用 int，则 index的增量为100，而不是1。

性能问题在于: 两个已排序的项之间没有“ in between”值。

item      index
-----------------
gizmo     1
<<------ Oh no! no room between 1 and 2.
This requires incrementing _every_ item after it
gadget    2
gear      3
toolkit   4
box       5

相反，应该这样做(下面是更好的解决方案) :

item      index
-----------------
gizmo     100
<<------ Sweet :). I can re-order 99 (!) items here
without having to change anything else
gadget    200
gear      300
toolkit   400
box       500

甚至更好: 这里是吉拉如何解决这个问题。它们的“ rank”(你称之为 index)是一个字符串值，允许在排名项目之间有大量的喘息空间。

下面是我使用的 jira 数据库的一个真实例子

   id    | jira_rank
---------+------------
AP-2405 | 0|hzztxk:
ES-213  | 0|hzztxs:
AP-2660 | 0|hzztzc:
AP-2688 | 0|hzztzk:
AP-2643 | 0|hzztzs:
AP-2208 | 0|hzztzw:
AP-2700 | 0|hzztzy:
AP-2702 | 0|hzztzz:
AP-2411 | 0|hzztzz:i
AP-2440 | 0|hzztzz:r

注意这个例子 hzztzz:i。字符串排名的优势在于，两个项目之间的空间已经用完，因此 还是不需要对其他任何项目进行重新排名。您只需开始向字符串追加更多字符以缩小焦点范围。

编辑: 正如注释中提到的，您不能在 0|hzztzz:和 0|hzztzz:a之间插入任何内容。我想这就是为什么我看到 jira 的数据库会定期在结尾附加 :i而不是 :a来避免这种情况的原因。如果你真的想防止问题，那么我 好好想想你可以改变你的算法，以便(例如)每次你将插入 :a在结束时，你代替插入 :ai。这样，您在逻辑上保证没有排名将以字母 a结束-这应该意味着您将始终有“空间”来插入更多的项目，而不必重新订购任何东西。

小开 
Page           Item
-----------    ---------------
PK | pid       PK, FK | pid
| name      PK     | index
| content

其中 index 可以是一个字符串(字典顺序) ，或者如果您希望进行数字排序(带间隔或不带间隔取决于特定用例) ，则使用 int

复合主键确保您可以相对于任何给定的 pid 使用本地索引，而不是使用问题中提到的全局“ iid”思想。

小开

为什么不像你建议的那样建立一个有序列表呢？

创建一个表示不同列表的“ Orderedlist”表。然后创建一个“ ListElement”表，该表具有指向下一个 listElement 的(可空的)自引用。OrderedList 表的实例将有一个指向 ListElement 表的实例“ StartingElement”的引用。

如果需要重新排序，只需从涉及的节点更新“ NextElement”引用;)

以防某些视觉效果有帮助: https://www.geeksforgeeks.org/data-structures/linked-list/

ListElement 表的巧妙排序可能有助于提高选择操作的性能。(例如，在重新生成列表时。递归可能也是一个想法)不知道你到底把什么叫做 FrontEnd 编程，但是你可以在 SQL 中创建函数来帮助你在检索数据之前得到结果。


提交答案