萬盛學電腦網

您现在的位置: 萬盛學電腦網 >> 程式設計 >  >> 資料庫 >> SQL Server 教學

以中值排序基數法實現 BBS 樹狀回覆結構 (免遞歸)

傳統 BBS 樹狀結構常用遞歸查詢,但會產生大量 SQL 查詢,效能不佳。本文介紹「中值排序基數法」,透過單一排序欄位 ordernum 配合深度 deep,以單次查詢即可完整呈現樹狀結構。

核心思想

在資料表新增三個冗餘欄位:

  • rootid:根文章 ID (0 表示根文章)
  • deep:回覆深度 (0 為根文章)
  • ordernum (float):排序基數,關鍵在於「取中值」

運作範例 (起始基數 64 = 2^6,實務建議用 65536 = 2^16)

idrootiddeepordernum動作
1000根文章
21164第一則回覆,基數 = 2^n
31132回覆第 1 篇,取 (0+64)/2 = 32
41248回覆第 3 篇,取 (32+64)/2 = 48
51356回覆第 4 篇,取 (48+64)/2 = 56
61240回覆第 3 篇,取 (32+48)/2 = 40

依 ordernum 遞增排序,配合 deep 即可呈現:

1
  3
    6
    4
      5
2

插入規則

  1. 根文章 ordernum = 0。
  2. 第一則回覆 ordernum = 2^n (如 65536)。
  3. 回覆「最後一則」:ordernum = 最後一則的 ordernum + 2^n。
  4. 回覆「中間則」:ordernum = (前一則 ordernum + 後一則 ordernum) / 2。

刪除 (剪枝)

找出下一個 deep ≤ 目標文章 deep 的文章,刪除兩者 ordernum 之間 (不含邊界) 的所有文章。

例:刪除文章 3 (ordernum=32, deep=1) 及其子樹。下一個 deep≤1 為文章 2 (ordernum=64)。刪除 ordernum 在 32~64 之間的文章 (3,6,4,5)。

顯示查詢

SELECT * FROM forum
ORDER BY rootid + id - SIGN(rootid)*id DESC, ordernum;

配合 deep 欄位即可輸出樹狀縮排。

預存程序範例 (新增文章)

CREATE PROCEDURE [add] @keyid int, @message varchar(50) OUTPUT
AS
IF (@keyid = 0)
    INSERT INTO forum (rootid, deep, ordernum, ...) VALUES (0, 0, 0, ...);
ELSE
BEGIN
    DECLARE @rootid int, @id int, @deep int, @begnum float, @endnum float, @ordernum float;
    SELECT @rootid=rootid, @id=id, @begnum=ordernum, @deep=deep FROM forum WHERE id=@keyid;
    IF (@id = 0)
    BEGIN
        SELECT @message = '要回覆的文章已被刪除!';
        RETURN;
    END
    -- 後續計算 @endnum 並取中值邏輯...
END
copyright © 萬盛學電腦網 all rights reserved