在有序数据表中实现多记录上移下移置顶置底算法思路

野性酷女 2021-12-15 17:29 400阅读 0赞

1.  ### 引言 ###
    
    数据库应用中常需要在一个有序数据子集中，对指定的若干条记录进行上下移动。例如，管理员需要对新闻列表中的若干条新闻置顶，考试出卷时需要对选定题目进行上下移动重排顺序，等等。
    
    总的应该场景在数据表中可以概括为如下模型：
    
    数据表 TblData(id,fid,rank)，id表示记录的唯一标识，fid指记录的父节点，rank代表父节点下兄弟的前后顺序，依次从1递增，没有空隙。
    
    问题是要对相同fid下选中的若干个节点进行上下移动，如图1中的2个示例：
    
    ![147456-20190223094800297-885855667.png][]
    
    图 1 上移操作示例图
    
    左侧示例是对第5、6两个连续的记录上移，右侧示例是对第4和6个有间隔的记录上移。上移后，要移动的记录间的间隔保持不变。现实中，选中记录的位置和数量都是随机的，移动方向有“上移”1位，“下移”1位，“置顶”和“置底”。该需求进入存储过程的参数可归结为  PROCEDURE Reorder(OUT out\_errno INT, IN in\_ids TEXT, IN in\_n INT UNSIGNED, IN in\_direction)，其中，out\_errno 用于返回状态码，in\_ids 是要移动的多个 id，以“,”分隔；in\_n 是要移动的 id 数量；in\_direction 是移动方向，取值是"up","down","top","bottom"。
2.  ### 上移操作 ###
    
    #### 以块为单位的上移 ####
    
    以向上移动（上移或置顶）为例（如图2所示），将连续的记录看作一个块，按升序依次对各块进行上移操作。示例中有3个块，因此需要移动3次。
    
    ![147456-20190223095856904-1551745373.png][]
    
    图2 上移操作块示意图
    
    #### 特定块的上移 ####
    
    对具体的块的移动，需要确定移动的步长(step)和块中的记录数(size)。通过第1块可以确定移动的步长，并且该步长对所有块都适用，即，所有块移动的步长都和第1块相同。图2中，如果进行“上移”，则移动的步长是 step = 1；如果进行“置顶”，则移动的步长是 step = 4。不同块中的记录数可能不同。图2中第1块的记录是5和6，因此记录数是 size = 2。
    
    以块1的“置顶”操作为例（如图3所示）。以要移动的记录5作为基准点，current=5，对其上面步长范围内的记录下移，并对其下面块中记录数范围内的记录上移，即，对\[current-step,current-1\]范围的记录作下移 (+size)，对\[current,current+size-1\]范围的记录上移 (-step)。
    
     ![147456-20190223104408133-1712104912.png][]
    
    图3 特定块的上移示意图
    
    该过程通过1条SQL语句可以实现：
    
    UPDATE TblData  
    SET rank=rank+IF(rank<current,size,-step)  
    WHERE fid=l\_fid -- 其中，l\_fid 是指记录共同的父节点编号  
    AND rank BETWEEN current-step AND current+size-1  
    
3.  ### 下移操作 ###
    
    下移过程和上移过程类似，区别是移动要从下面的块开始（即，编号大的块），与下面的记录进行交换（如图4所示）。
    
    ![147456-20190223111313598-467565006.png][]
    
    图4 特定块的下移示意图
4.  ### 以块为操作单位的可选方案 ###
    
    从前文可以看出，确定移动步长(step)和块内记录数(size)起到关键作用。 移动步长根据第1块（上移操作）或最后1块（下移操作）很容易确定。 但对于块内记录数却不那么容易，需要设置游标判断相邻两条记录是否连续，是否有间隙，还要进行记数，并在存在间隙时需要暂停，转去执行具体块的移动操作。 可选方案是对要移动的记录不作分块处理，即每条要移动的记录都看作一个块进行移动。 这样带来的后果是：
    
     *  图2示例中，若按块移动，则需移3次（因为有3个块需要上移）；若不分块移动，则需移动4次（因为有4条记录需要上移）。移动次数取决于块数和记录数的区别。
     *  图2示例中，若按块移动，则需要确定每1块的记录数（第1块是2，第2和3块都是1）；若不分块移动，则不需要确定每块记录数，或可以看成每块记录数都是1。是否省去了统计块内记录数的区别。
     *  效率上，主要取决于块数和记录数；逻辑上，后者更简单清晰。因此，本人倾向后者。
5.  ### 完整实现代码 ###
    
    使用MySQL存储过程实现上述功能，参考代码如下。假设传入参数在数据库外的合法性已经保证，数据库内的合法性需要验证；假设要移动的记录数大于0；假设数据表中记录都是有序连续的。
    
    DROP PROCEDURE IF EXISTS Reorder;  
    CREATE PROCEDURE Reorder(  
      OUT out\_errno INT,  
      IN in\_ids TEXT,  
      IN in\_n INT UNSIGNED,  
      IN in\_direction VARCHAR(16)  
    )  
    \-- block0 是整个程序最外层的范围，其中还包含 block1（检测合法性） 和 block2（实际移动操作）  
    block0: BEGIN  
      DECLARE  
          l\_rank\_max,  -- 用于记录最大Rank值，也即记录总数  
          l\_fid            -- 用于记录父节点编号  
      INT UNSIGNED;  
      -- block1 对传入参数在数据库端合法性进行检测  
      block1: BEGIN  
        -- 将要移动的记录存入临时表 t0(id,rank,processed)  
        -- 其中，processed用于block2中循环处理待移动记录的标记  
        IF TRUE THEN   
          DROP TEMPORARY TABLE IF EXISTS t0;  
          SET @sql = CONCAT('  
            CREATE TEMPORARY TABLE t0  
            SELECT id, rank,'no' processed  
            FROM TblData   
            WHERE id IN(',in\_ids,')  
            ORDER BY rank ',IF(in\_direction IN('up','top'),'ASC','DESC'),'   -- 要移动的记录，若上移，则按rank升序排列，否则降序  
          ');  
          PREPARE s FROM @sql;EXECUTE PREPARE s;DEALLOCATE PREPARE s;  
        END IF;  
        -- 101 检测要移动的记录是否都存在  
        IF (SELECT COUNT(id) FROM t0)<>in\_n THEN  
          SET out\_errno = 101;  
          LEAVE block0;  
        END IF;  
        -- 102 要移动的记录都隶属于同一父节点  
        IF (  
          SELECT COUNT(DISTINCT fid) FROM t0  
        )>1 THEN   
          SET out\_errno = 102;  
          LEAVE block0;  
        END IF;  
        SET l\_fid = (SELECT fid FROM t0 LIMIT 1);  
        SET l\_rank\_max = (SELECT MAX(rank) FROM TblData WHERE fid=l\_fid);  
      
        IF in\_direction IN('up','top') THEN  
          -- 103 如果上移，是否已经在顶端  
          IF (  
            SELECT rank=1 FROM t0   
            LIMIT 1  
          ) THEN   
            SET out\_errno = 103;  
            LEAVE block0;  
          END IF;  
        ELSE  
          -- 104 如果下移，是否已经在底端  
          IF (  
            SELECT rank=l\_rank\_max  
            FROM t0   
            LIMIT 1  
          ) THEN   
            SET out\_errno = 104;  
            LEAVE block0;  
          END IF;  
        END IF;  
      END block1;  
      
      block2: BEGIN  
        DECLARE l\_step, l\_size, l\_current INT UNSIGNED;  
        SET l\_size = 1;   
        IF in\_direction IN('up','top') THEN  
          -- 上移操作  
          SET l\_step = IF(  
            in\_direction='up',  
            1,  
            (SELECT rank-1 FROM t0 LIMIT 1)  
          );  
          myloopup: LOOP  
            -- 所有要移动的记录都已经处理完  
            IF NOT (  
              SELECT id FROM t0  
              WHERE processed='no'  
              LIMIT 1  
            ) THEN   
              LEAVE myloopup;  
            END IF;  
            -- 对要移动的记录 t0.processed='no' 的记录进行上移   
            SET l\_current = (SELECT rank FROM t0 WHERE processed='no' LIMIT 1);  
            UPDATE TblData  
            SET rank=IF(rank<l\_current,+l\_size,-l\_step)  
            WHERE fid=l\_fid  
            AND rank BETWEEN l\_current-l\_step AND l\_current+l\_size-1;  
            -- 设置标记位，表示已经处理过  
            UPDATE t0 SET processed='yes' WHERE processed='no' LIMIT 1;  
          END LOOP myloopup;  
        ELSE  
          -- 下移操作  
          SET l\_step = IF(  
            in\_direction='down',  
            1,  
            (SELECT l\_rank\_max-rank FROM t0 LIMIT 1)  
          );  
          myloopdown: LOOP  
            IF NOT(  
              SELECT id FROM t0  
              WHERE processed='no'  
              LIMIT 1  
            ) THEN   
              LEAVE myloopdown;  
            END IF;  
            SET l\_current = (SELECT rank FROM t0 WHERE processed='no' LIMIT 1);  
            UPDATE TblData  
            SET rank=rank+IF(rank>=l\_current,-l\_size,+l\_step)  
            WHERE fid=l\_fid  
            AND rank BETWEEN l\_current-l\_size+1 AND l\_current+l\_step;  
            -- 设置标记位，表示已经处理过  
            UPDATE t0 SET processed='yes' WHERE processed='no' LIMIT 1;  
          END loop myloopdown;  
        END IF;  
        SET out\_errno = 0; -- 表示移动完成  
      END block2;  
    END block0  
    
    
    上述源代码中，上移和下移的过程可以合并，但展示的逻辑会略复杂，相对难理解。读者若希望合并，可自行改写代码。

转载于:https://www.cnblogs.com/jyginger/p/10421553.html

[147456-20190223094800297-885855667.png]: /images/20211215/2bb72fd5be724e8d87f72d16b4d8b465.png
[147456-20190223095856904-1551745373.png]: /images/20211215/0824acf3d83542e098954ba2effb9987.png
[147456-20190223104408133-1712104912.png]: /images/20211215/26ca24af995542fc83d06568a37b8ab1.png
[147456-20190223111313598-467565006.png]: /images/20211215/f9cdf82d4b654ff89038eaca684ba1ed.png