用于解决树形结构存储的闭包表，凭什么能快速获取某个节点的祖先节点/父节点/子节点？

SELECT 祖先节点 FROM 闭包表 WHERE /* 缺失：祖先节点 = ? AND */ 后代节点 = '...' ORDER BY 距离 DESC

CREATE TABLE 闭包表 (
+   后代节点ID INT,
    祖先节点ID INT,
-   后代节点ID INT,
    这俩节点距离 INT,
-   PRIMARY KEY (祖先节点ID, 后代节点ID),
+   PRIMARY KEY (后代节点ID, 祖先节点ID)
);

-- -------- 原来的闭包表结构 --------

CREATE TABLE IF NOT EXISTS 原来的闭包表 (
  祖先 VARCHAR(16),
  后代 VARCHAR(16),
  距离 INT,
  PRIMARY KEY (祖先, 后代, 距离))
SELECT REPLACE(b.`name`, 'root', '根') 祖先,
       REPLACE(c.`name`, 'root', '根') 后代,
       a.distance 距离
  FROM category_tree a
  JOIN category b ON b.id = a.ancestor
  JOIN category c ON c.id = a.descendant;

-- -------- 修改后的闭包表结构 --------

CREATE TABLE IF NOT EXISTS 修改后闭包表 (
  后代 VARCHAR(16),
  祖先 VARCHAR(16),
  距离 INT,
  PRIMARY KEY (后代, 祖先, 距离))
SELECT REPLACE(b.`name`, 'root', '根') 后代,
       REPLACE(c.`name`, 'root', '根') 祖先,
       a.distance 距离
  FROM category_tree a
  JOIN category b ON b.id = a.descendant
  JOIN category c ON c.id = a.ancestor;

-- 1. 查找子节点
EXPLAIN SELECT 后代 FROM 原来的闭包表 WHERE 祖先 = '根' AND 距离 = 1; -- rows: 14 = COUNT(category)
EXPLAIN SELECT 后代 FROM 修改后闭包表 WHERE 祖先 = '根' AND 距离 = 1; -- rows: 54 = COUNT(category_tree)

-- 2. 查找父节点
EXPLAIN SELECT 祖先 FROM 原来的闭包表 WHERE 后代 = '电脑配件' AND 距离 = 1; -- rows: 54
EXPLAIN SELECT 祖先 FROM 修改后闭包表 WHERE 后代 = 'RTX3080' AND 距离 = 1; -- rows: 6 = 所在层数
-- 上面这行复杂度是 O(N)。若是 1000 层的节点获取父节点，需要扫 1000 行表。

-- 3. 查找祖先节点
EXPLAIN SELECT 祖先 FROM 原来的闭包表 WHERE 后代 = '电脑配件' ORDER BY 距离 DESC; -- rows: 54
EXPLAIN SELECT 祖先 FROM 修改后闭包表 WHERE 后代 = 'RTX3080' ORDER BY 距离 DESC; -- rows: 6

-- 4. 查找后代节点（下面查的，实际是最后一层，没后代的）
EXPLAIN SELECT 后代 FROM 原来的闭包表 WHERE 祖先 = 'RTX3080'; -- rows: 1
EXPLAIN SELECT 后代 FROM 修改后闭包表 WHERE 祖先 = 'RTX3080'; -- rows: 54

CREATE TABLE 闭包表 (
    祖先 INT,
    后代 INT,
    距离 INT,
    PRIMARY KEY (后代, 距离),
    KEY (祖先, 距离)
);

PRAGMA cache_size = -204800; -- 允许 SQLite 缓存 200 MB

-- 闭包表查询
SELECT COUNT(*), SUM(code), SUM(CHAR_LENGTH(name)) -- SQLite 写法：SUM(LENGTH(name))
  FROM closure_tree
 FORCE INDEX (idx_closure_tree) -- 我这测试，MySQL 不加这行，耗时翻好几倍。SQLite 需去掉此行
  JOIN closure ON id = descendant
 WHERE ancestor = 0;

-- 递归邻接表查询
WITH RECURSIVE
  find(id, code, name, is_leaf) AS (
    SELECT id, code, name, is_leaf
      FROM adjacent
     WHERE pid = 0
     UNION ALL
    SELECT b.id, b.code, b.name, b.is_leaf
      FROM find a
      JOIN adjacent b ON NOT a.is_leaf AND b.pid = a.id
  )
SELECT COUNT(*), SUM(code), SUM(CHAR_LENGTH(name)) -- SQLite 写法：SUM(LENGTH(name))
  FROM find;

-- 理想中，没有递归损耗的邻接表查询
SELECT COUNT(*), SUM(b.code), SUM(CHAR_LENGTH(b.name)) -- SQLite 写法：SUM(LENGTH(b.name))
  FROM adjacent a
  LEFT JOIN adjacent b ON b.pid = a.id -- SQLite 需要 LEFT JOIN，否则耗时翻几倍
 WHERE NOT a.is_leaf;

PRAGMA cache_size = -204800; -- 允许 SQLite 缓存 200 MB

-- 闭包表查询
SELECT COUNT(*), SUM(code), SUM(CHAR_LENGTH(name)) -- SQLite 写法：SUM(LENGTH(name))
  FROM closure_tree
 FORCE INDEX (idx_closure_tree) -- 我这测试，MySQL 不加这行，耗时翻好几倍。SQLite 需去掉此行
  JOIN closure ON id = descendant
 WHERE ancestor = 0
   AND distance = 5;

-- 递归邻接表查询
WITH RECURSIVE
  var(depth) AS (
    SELECT 5
  ),

  -- 递归部分查前 N - 1 层
  find(id, is_leaf, depth) AS (
    SELECT 0, FALSE, var.depth - 1
      FROM var
     UNION ALL
    SELECT b.id, b.is_leaf, a.depth - 1
      FROM find a
      JOIN adjacent b ON b.pid = a.id
     WHERE a.depth > 0
       AND NOT a.is_leaf
  )

-- 最后一次性 JOIN 第 N 层
SELECT COUNT(*), SUM(b.code), SUM(CHAR_LENGTH(b.name)) -- SQLite 写法：SUM(LENGTH(b.name))
  FROM find a
 CROSS JOIN adjacent b ON a.id = b.pid -- SQLite 要加 CROSS，否则耗时翻几倍
 WHERE a.depth = 0;

-- 理想中，没有递归损耗的邻接表查询（需要根据层数 N，动态生成 SQL）
SELECT COUNT(*), SUM(t5.code), SUM(CHAR_LENGTH(t5.name)) -- SQLite 写法：SUM(LENGTH(t5.name))
  FROM adjacent t1
  JOIN adjacent t2 ON t2.pid = t1.id
  JOIN adjacent t3 ON t3.pid = t2.id
  JOIN adjacent t4 ON t4.pid = t3.id
  JOIN adjacent t5 ON t5.pid = t4.id
 WHERE t1.pid = 0;

-- 允许 200 MB 的内存表
SET max_heap_table_size = 200 << 20;

-- 建临时数据表，装载 csv 数据，以及计算序号和父子关系
CREATE TABLE data (
    code    BIGINT      NOT NULL,
    p_code  BIGINT      NOT NULL,
    type    TINYINT     NOT NULL,
    name    VARCHAR(25) NOT NULL,
    id      INT         NOT NULL,
    pid     INT         NOT NULL,
    PRIMARY KEY (code) USING BTREE,
    INDEX USING BTREE (id),
    INDEX USING BTREE (pid, id)
) ENGINE = MEMORY;

-- 加载 csv
LOAD DATA INFILE 'area_code_2022.csv'
INTO TABLE data
CHARACTER SET UTF8MB4
FIELDS TERMINATED BY ','
ENCLOSED BY '"'
(code, name, type, p_code);

-- 按照 code 顺序计算 id
UPDATE data
  JOIN (SELECT code, ROW_NUMBER() OVER win row_num
          FROM data
        WINDOW win AS (ORDER BY code)) t USING(code)
   SET id = row_num;

-- 计算 parent_id（不存在的标0）
UPDATE data a
  LEFT JOIN data b ON b.code = a.p_code
   SET a.pid = IFNULL(b.id, 0);

-- 建邻接表，并从临时数据表填充数据
CREATE TABLE adjacent (
    id      INT         NOT NULL,
    pid     INT         NOT NULL,
    is_leaf BOOL        NOT NULL,
    type    TINYINT     NOT NULL,
    code    BIGINT      NOT NULL,
    name    VARCHAR(25) NOT NULL,
    PRIMARY KEY (pid, id)
)
SELECT -1 pid, 0 id, FALSE is_leaf, 0 type, 0 code, '' name
 UNION ALL
SELECT pid, id, type = 5 is_leaf, type, code, name
  FROM data;

-- 建闭包表主表，并从临时数据表填充数据
CREATE TABLE closure (
    id      INT         NOT NULL,
    type    TINYINT     NOT NULL,
    code    BIGINT      NOT NULL,
    name    VARCHAR(25) NOT NULL,
    PRIMARY KEY (id)
)
SELECT 0 id, 0 type, 0 code, '' name
 UNION ALL
SELECT id, type, code, name
  FROM data;

-- 建闭包表树形关系表
CREATE TABLE closure_tree (
    ancestor    INT     NOT NULL,
    descendant  INT     NOT NULL,
    distance    TINYINT NOT NULL,
    PRIMARY KEY (descendant, distance)
);

-- 递归构建树形关系
INSERT INTO closure_tree(ancestor, descendant, distance)
WITH RECURSIVE
  parent_of(orig_id, id, dist) AS (
    SELECT id, id, 0
      FROM data
     UNION ALL
    SELECT orig_id, pid, dist + 1
      FROM parent_of
      JOIN data USING(id)
     WHERE id
  )
SELECT id, orig_id, dist
  FROM parent_of;

-- 为闭包表树形关系表建二级索引
CREATE INDEX idx_closure_tree ON closure_tree (ancestor, distance);

-- 丢弃临时数据表
DROP TABLE data;

#!/bin/bash

sqlite3 :memory: <<'EOF'

-- 在内存中计算，最后整理紧凑才写入文件
PRAGMA TEMP_STORE = MEMORY;

-- 导入 csv 文件至临时表
CREATE TEMP TABLE csv (code INTEGER PRIMARY KEY, name TEXT, type INT, p_code INT);
.import --csv area_code_2022.csv csv

-- 建邻接表
CREATE TABLE adjacent (
    id      INT     NOT NULL,
    pid     INT     NOT NULL,
    is_leaf INT     NOT NULL,
    type    INT     NOT NULL,
    code    INT     NOT NULL,
    name    TEXT    NOT NULL,
    PRIMARY KEY (pid, id)
) WITHOUT ROWID;

-- 填充邻接表
INSERT INTO adjacent (pid, id, is_leaf, type, code, name)
SELECT -1, 0, FALSE, 0, 0, ""
 UNION ALL
SELECT p_code, ROW_NUMBER() OVER (), type = 5, type, code, name
  FROM csv
 ORDER BY code;

-- 建临时索引，提速 code 搜索
CREATE INDEX i ON adjacent (code);

-- 更新 pid
UPDATE adjacent
   SET pid = t2.id
  FROM adjacent t2
 WHERE adjacent.pid = t2.code;

-- 丢弃临时索引
DROP INDEX i;

-- 建 id -> pid 索引
CREATE INDEX idx_adjacent_id ON adjacent (id);

-- 建闭包表主表
CREATE TABLE closure (
    id      INTEGER PRIMARY KEY,
    type    INT     NOT NULL,
    code    INT     NOT NULL,
    name    TEXT    NOT NULL
);

-- 建闭包表树形关系表
CREATE TABLE closure_tree (
    ancestor    INT NOT NULL,
    descendant  INT NOT NULL,
    distance    INT NOT NULL,
    PRIMARY KEY (descendant, distance)
) WITHOUT ROWID;

-- 填充闭包表主表
INSERT INTO closure (id, type, code, name)
SELECT id, type, code, name
  FROM adjacent;

-- 递归构建树形关系
WITH RECURSIVE
  parent_of(orig_id, id, dist) AS (
    SELECT id, id, 0
      FROM adjacent
     UNION ALL
    SELECT orig_id, pid, dist + 1
      FROM parent_of
      JOIN adjacent USING(id)
     WHERE id
  )
INSERT INTO closure_tree (ancestor, descendant, distance)
SELECT id, orig_id, dist
  FROM parent_of;

-- 为闭包表树形关系表建二级索引
CREATE INDEX idx_closure_tree ON closure_tree (ancestor, distance);

-- 整理紧实数据库后，写入磁盘
ANALYZE;
VACUUM INTO 'test.db';

EOF