推薦人機制相信大家都不陌生，多多少少都有遇過，有些網站可能在註冊會員時會有一欄可以填寫推薦人，概念大致上如下：

User A 首先加入，他覺得這個服務很棒於是推薦給 User B 和 User C， User B 也感受到了服務帶給他的便利，於是推薦給 User D 和 User E，這跟老鼠會有 87% 像。

今天在吃水餃看新聞的時候，推薦人機制從我腦中呼嘯而過，就邊吃水餃邊想，如果是我，我要怎麼設計出一個有推薦人機制的會員系統？一開始想說用個 mapping table 就可以了事，但仔細一想，這樣 query 會寫不完呀！

畢竟是老鼠會推薦人機制，你會想要知道因為 User A 而進來的會員究竟有哪些人，以上面的例子來講就是

   User B             User C
   /    \
User D   User E

總共有四個人是因為 User A 而註冊的。

Trivial method

假設我們今天用最簡單的方法，建立一張 parent-child 的表來記錄推薦人。

create table `referral` (
    `id` int(11) NOT NULL AUTO_INCREMENT,
    `parent` varchar(63) DEFAULT NULL,
    `child` varchar(63) DEFAULT NULL,
    PRIMARY KEY (`id`)
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8;

那根據上面例子所建的表就會如下：

問題來了：想要知道因為 User A 而進來的會員究竟有哪些人？

SELECT child FROM `referral` WHERE parent='userA'; -- root
SELECT child FROM `referral` WHERE parent='userB'; -- level 1
SELECT child FROM `referral` WHERE parent='userC'; -- level 2
SELECT child FROM `referral` WHERE parent='userD'; -- level 2

你能想像當你系統的推薦人層數成長後，query 的複雜度也會隨之提高，必然得用遞迴的方式下去查詢，如此一來對於 DB 的負擔也就加重了。

但其實觀察一下 Figure 1，可以發現推薦人機制本身就是樹狀結構的東西，所以如果使用一個本性相符的方法，可能會比較適合一點。

Nested set model

Nested set model 就是一個適合處理樹狀結構資料的資料模型，它的特性剛好都是推薦人機制需要的東西：

• 不需要遍歷整顆樹
• 有效率的獲取節點
• 有效率的計算節點數量

由 Figure 2 可以發現，每個 User 旁邊都多了兩個數字，分別是 left 和 right，這是 Nested set model 的特別之處。假設一開始只有 UserA

再來加入 UserB 時會變成

接著加入 UserC

最後再加一層，加入 UserD

再回到 「因為 User A 而進來的會員究竟有哪些人？」 這個問題，你會發現我們只需要

SELECT * FROM `referral` WHERE `username`='userA';
SELECT * FROM `referral` WHERE `lft` > 1 and `rgt` < 8;

使用 Nested set model 後我們只需要做一次查詢，不管推薦人的層數有幾層，但如果是 Trivial method ，有幾層就要 query 幾次，這個感受度一下就有了。

如何建構一顆樹

Nested set model 有幾個重要的欄位，分別是 lft、rgt、level 、parent_id 和 tree_id，至於其他的欄位就因應用而異了。

CREATE TABLE `referral` (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(20) NOT NULL,
  `lft` int(11) NOT NULL,
  `rgt` int(11) NOT NULL,
  `level` int(11) NOT NULL,
  `tree_id` int(11) DEFAULT NULL,
  `parent_id` int(11) DEFAULT NULL,
  `user_id` int(11) NOT NULL,
  PRIMARY KEY (`id`),
  UNIQUE KEY `username` (`username`),
  KEY `parent_id` (`parent_id`),
  KEY `referral_level_idx` (`level`),
  KEY `referral_lft_idx` (`lft`),
  KEY `referral_rgt_idx` (`rgt`),
  CONSTRAINT `referral_ibfk_1` FOREIGN KEY (`parent_id`) REFERENCES `referral` (`id`) ON DELETE CASCADE
) ENGINE=InnoDB AUTO_INCREMENT=8 DEFAULT CHARSET=utf8;

或許有人會疑惑 tree_id 的用途，這是用來支援 Multi-tree 時使用的，試想有些人一開始註冊時可能沒有推薦人，但之後卻將服務推薦給別人，這時候他就會自成一顆樹。

當然 Nested set model 不只可以用在推薦人機制上，只要是任何長得像樹的東西，都可以試試看。