推薦人與 Nested model set

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

Figure 1. 推薦人示意圖

User A 首先加入,他覺得這個服務很棒於是推薦給 User BUser CUser B 也感受到了服務帶給他的便利,於是推薦給 User DUser 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;

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

id parent child
1 userA userB
2 userA userC
3 userB userD
4 userB userE

問題來了:想要知道因為 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

Figure 2. Nested set model

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

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

由 Figure 2 可以發現,每個 User 旁邊都多了兩個數字,分別是 leftright,這是 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 有幾個重要的欄位,分別是 lftrgtlevel
parent_idtree_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 不只可以用在推薦人機制上,只要是任何長得像樹的東西,都可以試試看。

Show Comments