在数据库中高效地存储项目位置(用于排序)

32

场景:

有一个电影数据库,用户拥有的电影会在名为“我的电影”的页面上展示,这些电影可以按照用户所需顺序进行展示。例如,“搏击俱乐部”在第1个位置,“蓝色马赛回忆”在第3个位置等等。

显而易见的解决方案是为每个项目存储位置信息,例如:

movieid, userid, position
1 | 1 | 1
2 | 1 | 2
3 | 1 | 3

然后在输出数据时按位置排序。这种方法在输出方面表现良好,但更新时存在问题:如果更改某个项目的位置,则所有其他位置都需要更新,因为位置是相对的。如果电影编号#3现在处于第2个位置,则必须将其更新到第2个位置。如果数据库包含10,000部电影,并且一部电影从第1个位置移动到第9999个位置,那么几乎需要更新10,000行!

我唯一的解决方案是单独存储定位,而不是为每个项目都单独存储位置字段,而是在运行时使用一组大的位置数据转储,并与每个项目相关联(JSON、XML或其他方式)。但这种做法效率不高,因为无法让数据库进行排序。

我的问题总结:在友好获取和更新的前提下,最有效的方法是如何存储列表中项目的位置?


类似问题:https://dev59.com/3Gkw5IYBdhLWcg3w9vJ- - Venryx
6个回答

18

2022年8月:请注意,下面的方法存在缺陷,并且在将电影向下移动列表时不起作用。我已经发布了一个新答案,解决了这个问题。

如果您使用用户放置电影在给定位置的时间戳和位置的组合,而不是尝试维护实际位置,则可以实现一种相当简单的SELECT和UPDATE数据的方法。例如,基本数据集:

create table usermovies (userid int, movieid int, position int, positionsetdatetime datetime)

insert into usermovies (userid, movieid, position, positionsetdatetime)
values (123, 99, 1, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (123, 98, 2, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (123, 97, 3, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (123, 96, 4, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (123, 95, 5, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (123, 94, 6, getutcdate())

insert into usermovies (userid, movieid, position, positionsetdatetime)
values (987, 99, 1, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (987, 98, 2, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (987, 97, 3, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (987, 96, 4, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (987, 95, 5, getutcdate())
insert into usermovies (userid, movieid, position, positionsetdatetime)
values (987, 94, 6, getutcdate())

如果您使用以下查询来查询用户的电影:

;with usermovieswithrank as (
  select userid
  , movieid 
  , dense_rank() over (partition by userid order by position asc, positionsetdatetime desc) as movierank
  from usermovies
)
select * from usermovieswithrank where userid=123 order by userid, movierank asc

那么您将获得预期的结果:

USERID  MOVIEID     MOVIERANK
123     99          1
123     98          2
123     97          3
123     96          4
123     95          5
123     94          6

为了移动电影排名中的一部电影,我们需要更新位置和positionsetdatetime列。例如,如果用户ID为123将电影95从排名5移动到排名2,则执行以下操作:

update usermovies set position=2, positionsetdatetime=getutcdate() 
where userid=123 and movieid=95 

使用上述UPDATE查询后,将导致以下结果:

USERID  MOVIEID     MOVIERANK
123     99          1
123     95          2
123     98          3
123     97          4
123     96          5
123     94          6

如果用户ID为123将电影96移动到排名1:

update usermovies set position=1, positionsetdatetime=getutcdate()
where userid=123 and movieid=96 

我们得到:

USERID  MOVIEID     MOVIERANK
123     96          1
123     99          2
123     95          3
123     98          4
123     97          5
123     94          6

当然,您将在usermovies表中拥有重复的位置列值,但是使用此方法,您永远不会显示该列,您只需将其与positionsetdatetime一起使用,以确定每个用户的排序排名,而您确定的排名是真实的位置。

如果您希望在某个时刻,position列正确反映电影排名而不参考positionsetdatetime,则可以使用上面选择查询中的movierank来更新usermovies的position列值,因为它实际上不会影响确定的电影排名。


3
刚刚注意到这个问题已经一年了,哎呀!不过没关系,也许我的建议能帮助别人 :-) - Elliveny
2
如果用户将电影向下移动,这种方法就不起作用了。例如,如果他们将第98部电影从第4个位置移动到第6个位置,那么将会有两部电影在第6个位置,但是由于其更近的位置设置时间,电影98将首先显示(在第5个位置)。 - bergie3000
@bergie3000 您是正确的 - 我很抱歉错过了这一点!我猜想在向下移动时,通过将所需位置加1来轻松解决它;因此,在您的示例中,将电影98从位置4设置为位置7(即所需位置6加1)就可以了,我认为? - Elliveny
不,忘了那个建议吧;它需要比那更多的关注。我会看看我能想出什么! - Elliveny
1
@WongJiaHau - 感谢您的评论,它促使我再次审视这个问题并尝试解决您所描述的问题。 - Elliveny
显示剩余4条评论

12

我一直在苦恼如何处理这种情况,现在意识到迄今为止最好的解决方案是按照您想要的顺序列出电影的列表或数组,例如:

用户ID,电影顺序

1:[4,3,9,1...]

显然,您将对数组进行序列化。

'感觉...效率不高'?

如果考虑用户有100部电影的列表。按位置搜索将需要一个数据库查询、一个字符串转换为数组以及接下来的moviesOrder[index]操作。可能比纯粹的数据库查找慢,但仍然非常非常快。

另一方面,请考虑如果您更改了顺序;

如果使用数据库中存储的位置,则需要进行高达100次行更改,而使用数组splice则不需要。链表的想法很有趣,但所呈现的方式行不通——如果单个元素失效,所有内容都将被破坏,并且看起来速度也慢得多。其他想法,比如留下间隔、使用浮点数,虽然可行,但会很混乱,并且在某些时候容易失败,除非您进行垃圾回收。

似乎应该有更好的方法在SQL中实现,但实际上并没有。


我喜欢这个原因是,如果您考虑一下,子项的排序属于父项。在真空中,一行具有“order”属性为“5”意味着什么?您必须看到所有其他行才能了解其含义。 - Nick Manning
我认为我自己也更喜欢这样...我们需要确保如果电影被删除,我们也要更新它 - msanjay
唯一的问题是一个带有 order by 的查询...我们必须在查询后对数据进行排序...(除非有一些花哨的 SQL 可以拆分字符串并完成所有操作) - msanjay

7

以链表的形式存储订单。不要保存绝对的位置,而是保存前一项的ID。这样,任何更改只需要更新两行。

movieid | userid  | previousid
   1    |    1    | 
   2    |    1    |    1
   3    |    1    |    4
   4    |    1    |    2

为了按顺序获取电影...
请提供更多上下文以获得更准确的翻译。
SELECT movieid WHERE userid = 1 ORDER BY previousid

-> 1, 2, 4, 3

将#4向上移动一个位置:

DECLARE @previousid int, @currentid int
SET @previousid = SELECT previousid FROM movies WHERE movieid = @currentid

-- current movie's previous becomes its preceding's preceding
UPDATE movies SET previousid = 
    (SELECT previousid FROM movies WHERE movieid = @previousid)
WHERE movieid = @currentid

-- the preceding movie's previous becomes the current one's previous
UPDATE movies SET previousid = @currentid WHERE movieid = @previousid

这仍然需要1次读取和2次写入,但是比10000次写入要好。


@bjan 选择应该相当简单...更新有点棘手,但我认为那样可以。 - McGarnagle
根据我的测试,它会导致重复的previousid!! - bjan
3
查询按顺序获取电影的方法似乎不太有效。考虑以下数据:(id,prev):(1,2),(2,3),(3,_). 这个查询将返回 3, 1, 2,但正确结果应该是 3, 2, 1。鉴于您的模式,似乎没有一个很好的(非递归、单扫描)纯SQL查询方式来解决这个问题。不过,如果您改为选择 SELECT movieid, previousid WHERE userid = 1,那么在其他编程语言中排序它们就变得非常简单了。 - Joe K
3
@McGarnagle 的 UPDATE 看起来很简单,但是没有简单的方法来进行 SELECT 查询。 - Afanasii Kurakin
@McGarnagle 这不更像是栈的风格吗?实际上,链表的风格会更高效和功能强大吧?(id、prev、next) - cmak
显示剩余2条评论

2

这里有一些非常有趣的解决方案。另一个可能性是将位置存储在一些空间中,比如10或100的倍数。

ID   NAME  POSITION
7     A       100
9     B       200
13    C       300
15    D       400
21    F       500

每次添加新的内容时,都可以进行100的倍数操作。 将行C移动到位置1,将会使当前值减1或在当前值后加1。甚至可以减50,以便将来可能实现相同的操作。

ID   NAME  POSITION
7     A       100
9     B       200
13    C       50
15    D       400
21    F       500

这可以继续进行,在移动太多而不可能时,再次对所有行重新排序。

我在另一个类似的答案中看到,Atlassian 在 Jira 中使用字母代替数字进行词典排序...并且通过在特定位置前缀或附加字符来轻松更改顺序。如果我们搜索一下,会有更多的信息。 - msanjay
1
只是一个小提示,更有效的方法是从0开始,并使用2的幂增量,如128或1024。这样,您可以最大化更新计数而无需重新编号,前提是始终在现有值之间评估一半。对于所有用户排序方案,这应该足够了,因为给定int达到2G时,按1024排序会使您获得超过顺序值溢出的2M个项目。这比用户可管理的数量要大得多(可能是数千个?)。在将某些内容移动到顶部的情况下,还可以使用负值。 - Spook
2
Atlassian 在 Jira 中使用字母而非数字进行词典排序,这就是他们使用 LexoRank 的原因 → https://confluence.atlassian.com/adminjiraserver/managing-lexorank-938847803.html#:~:text=LexoRank%20is%20ranking%20system%20that,key%20areas%20of%20LexoRank%20administration. - Jake

1

继我在2014年的回答之后,我最终回到了这个问题,并建立在我之前的方法和其致命缺陷基础上。我提出了以下解决方案,使用SQL Server存储过程来展示逻辑。

首先,是电影表:

CREATE TABLE [dbo].[usermovies]
    ([userid] [int], [movieid] [int], [position] [int], [subposition] [int]) 

还有测试数据。请注意,当我们加载数据时,初始电影排名设置在位置列中,子位置设置为0:

insert into usermovies (userid, movieid, position, subposition)
values (123, 99, 1, 0)
      ,(123, 98, 2, 0)
      ,(123, 97, 3, 0)
      ,(123, 96, 4, 0)
      ,(123, 95, 5, 0)
      ,(123, 94, 6, 0)
      ,(987, 99, 1, 0)
      ,(987, 98, 2, 0)
      ,(987, 97, 3, 0)
      ,(987, 96, 4, 0)
      ,(987, 95, 5, 0)
      ,(987, 94, 6, 0)

重要的是要理解每部电影(movierank)的排名不是根据位置值确定的,而是根据记录按位置和次位置排序后行的排名确定的。我创建了一个视图来提供movierank:

CREATE OR ALTER VIEW vwUserMoviesWithRank 
as
with userMoviesWithRanks as (
  SELECT *
   , dense_rank() over (partition by userid order by position asc, subposition asc) as movierank
  FROM usermovies
)
SELECT * FROM userMoviesWithRanks
GO

每个用户只能有一个具有给定位置/子位置值的电影,因为这提供了唯一的电影排名。向表中添加一个唯一的聚集索引可以很好地强制执行此规则,并且在有足够数据的情况下,还可以实现更快的数据访问。

CREATE UNIQUE CLUSTERED INDEX [IX_usermovies] 
    ON [dbo].[usermovies] ([userid] ASC, [position] ASC, [subposition] ASC)

下面的存储过程执行更新操作,允许用户更改电影排名。我已经添加了注释以帮助解释逻辑:
CREATE OR ALTER PROC proc_ChangeUserMovieRank
@userID int,
@movieID int,
@moveToRank int
as

DECLARE @moveFromRank int

DECLARE @movieIDAtNewRank int
DECLARE @positionAtNewRank int
DECLARE @subpositionAtNewRank int

IF @moveToRank<1 THROW 51000, '@moveToRank must be >= 1', 1;

BEGIN TRAN

-- Get the current rank of the movie being moved
SELECT @moveFromRank=movierank FROM vwUserMoviesWithRank WHERE userid=@userID and movieid=@movieID 

IF @moveFromRank<>@moveToRank BEGIN
  -- Get the position and subposition of the movie we need to shift down the list  
  -- if this move is decreasing the movie rank then we need to shift the movie at @moveToRank
  -- if this move is increasing the movie rank then we need to shift the movie at @moveToRank+1, to accommodate the removal
  SELECT @positionAtNewRank=position, @subpositionAtNewRank=subposition 
  FROM vwUserMoviesWithRank 
  WHERE userid=@userID and movierank=(@moveToRank + CASE WHEN @moveToRank>@moveFromRank THEN 1 ELSE 0 END)

  IF @positionAtNewRank IS NULL BEGIN 
    -- No movie needs to be updated, so we're adding to the end of the list
    -- Our destination is the position+1 of the highest ranked movie (with subposition=0)
    SELECT @positionAtNewRank=max(p.position)+1, @subpositionAtNewRank=0
      FROM vwUserMoviesWithRank p WHERE p.userid=@userID
  END ELSE BEGIN
    -- Move down (increase the subposition of) any movies with the same position value as the destination rank
    UPDATE m
    SET subposition=subposition+1
    FROM usermovies m
    WHERE userid=@userID AND position=@positionAtNewRank and subposition>=@subpositionAtNewRank
  END

  -- Finally move the movie to the new rank
  UPDATE m
  SET position=@positionAtNewRank, subposition=@subpositionAtNewRank
  FROM usermovies m
  WHERE m.userid=@userID AND m.movieid=@movieID
END
COMMIT TRAN
GO

这是使用上述测试数据进行的测试运行。电影列表使用以下SELECT语句列出,为了简洁起见,我没有在下面每次重复。这是我们的电影排名:
SELECT movieid, movierank FROM vwUserMoviesWithRank WHERE userid=123 ORDER BY movierank

movieid     movierank
----------- --------------------
99          1
98          2
97          3
96          4
95          5
94          6

将电影98移动到第5名:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=98, @moveToRank=5
movieid     movierank
----------- --------------------
99          1
97          2
96          3
95          4
98          5
94          6

将电影94移至排名第2:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=94, @moveToRank=2
movieid     movierank
----------- --------------------
99          1
94          2
97          3
96          4
95          5
98          6

将电影95移到排名第1位:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=95, @moveToRank=1
movieid     movierank
----------- --------------------
95          1
99          2
94          3
97          4
96          5
98          6

将电影99移动到第4名:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=99, @moveToRank=4
movieid     movierank
----------- --------------------
95          1
94          2
97          3
99          4
96          5
98          6

将电影97移动到第6名:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=97, @moveToRank=6
movieid     movierank
----------- --------------------
95          1
94          2
99          3
96          4
98          5
97          6

将电影97移动到排名4:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=97, @moveToRank=4
movieid     movierank
----------- --------------------
95          1
94          2
99          3
97          4
96          5
98          6

将电影95移动到第4名:

EXEC proc_ChangeUserMovieRank @userID=123, @movieID=95, @moveToRank=4
movieid     movierank
----------- --------------------
94          1
99          2
97          3
95          4
96          5
98          6

我认为这一切看起来都很好。

请注意,在执行这些操作后,位置/子位置数据现在如下所示:

select * from vwUserMoviesWithRank WHERE userid=123 order by movierank

userid      movieid     position    subposition movierank
----------- ----------- ----------- ----------- --------------------
123         94          3           0           1
123         99          4           0           2
123         97          4           1           3
123         95          4           2           4
123         96          4           3           5
123         98          6           0           6

这些值与确定的电影排名相差很大。

当电影排名发生变化时,该位置可能会在多行中变得相同,例如上面的第4个位置。当发生这种情况时,排名变化时需要更新更多的行,因此建议定期将位置和子位置重置为movierank值:

UPDATE usermovies
SET position=vwUserMoviesWithRank.movierank, subposition=0
FROM vwUserMoviesWithRank
INNER JOIN usermovies on usermovies.userid=vwUserMoviesWithRank.userid AND usermovies.movieid=vwUserMoviesWithRank.movieid
WHERE usermovies.position<>vwUserMoviesWithRank.movierank OR usermovies.subposition<>0

这个非常高效,而且能够很好地扩展,我认为所有的都运行正常,如果你有不同看法,请告诉我,我会再次查看(这次我不会等待8年!)

另外,我想指出我尝试在这里添加一个 SQL Fiddle 链接,但似乎他们目前没有 SQL Server 主机 :-/


1
ID   NAME  POSITION
7     A       1
9     B       2
13    C       3
15    D       4
21    F       5

如果我们想将项目D移动到位置2,则可以搜索2(我们要移动项目的位置)和4(项目当前位置)之间的间隔,并编写查询以在此间隔内的每个元素的位置上添加+1,因此在这种情况下,我们可以执行以下步骤:
  1. 搜索位置>= 2且位置<4的间隔中的项目,并将其位置加1
  2. 将项目D的位置设置为2。
这将生成以下结果: A->1, B->3, C->4, D->2, F->5
如果我们想要将B移动到D,则需要相反地应用-1。
  1. 搜索位置> 2且位置<= 4的间隔中的项目,并将其位置减1
  2. 将项目位置设置为4
从表中删除项目时,我们需要更新其位置大于正在被删除元素位置的每个项目。
创建项目时,其位置等于每个项目的计数+1。
免责声明:如果您有非常大的数量,也许这个解决方案不适合您,但对于大多数情况来说,它是可以的。通常情况下,用户不会将项目从第10000个位置移动到第2个位置,但是如果用户删除项目1,则查询将从剩余9999个项目中减去-1。如果这是您的情况,则使用链接列表的解决方案可能是最好的选择,但是排序将更具挑战性,因为您需要逐个查看谁在列表上的下一个项目。
示例查询
-- MOVE DOWN
UPDATE movie SET position = position-1  WHERE position <= 18 AND position > 13 AND id > 0;
UPDATE movie SET position = 18 WHERE id = 130;

-- MOVE UP
UPDATE movie SET position = position+1  WHERE position < 18 AND position >= 13 AND id > 0;
UPDATE movie SET position = 13 WHERE id = 130;

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接