1 如何在數(shù)據(jù)庫(kù)中存儲(chǔ)層級(jí)結(jié)構(gòu)

(1) 鄰接表模型

• 求節(jié)點(diǎn)的路徑
  舉例來(lái)說(shuō)，“Cherry”所在的路徑為Food > Fruit > Red > Cherry。在這里，我們可以從Cherry開(kāi)始查起，然后遞歸查詢(xún)查詢(xún)節(jié)點(diǎn)前的節(jié)點(diǎn)，直到某節(jié)點(diǎn)的父節(jié)點(diǎn)ID為0(Food)。

• 優(yōu)點(diǎn)
  簡(jiǎn)單易懂

• 缺點(diǎn)
  執(zhí)行起來(lái)效率低下。我們對(duì)于每個(gè)結(jié)果，期望只需要一次查詢(xún)；可是當(dāng)使用鄰接表模型時(shí)嵌套的遞歸使用了多次查詢(xún)，當(dāng)樹(shù)很大的時(shí)候，這種慢就會(huì)表現(xiàn)得尤為明顯。

上帝是公平的，當(dāng)在執(zhí)行時(shí)效率低下，意味著可以增加預(yù)處理的程度。

(2）MPTT(修改過(guò)的前序遍歷算法)

• 原理
  現(xiàn)在我們把樹(shù)“橫”著放。如下圖所示，我們首先從根節(jié)點(diǎn)（“Food”）開(kāi)始，先在它左側(cè)標(biāo)記“1”，然后我們到“Fruit”，左側(cè)標(biāo)記“2”，接著按照前序遍歷的順序遍歷完樹(shù)，依次在每個(gè)節(jié)點(diǎn)的左右側(cè)標(biāo)記數(shù)字。

• 實(shí)現(xiàn)

• 打印樹(shù)
  如果要想打印樹(shù)，你只需要知道你要檢索的節(jié)點(diǎn)。比如，想要打印“Fruit”的子樹(shù)，可以查詢(xún)左數(shù)大于2而小于11的節(jié)點(diǎn)。

SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;

• 求節(jié)點(diǎn)的路徑
  對(duì)于某節(jié)點(diǎn)，我們只需求出左數(shù)值小于其左數(shù)值、右數(shù)大于其右數(shù)的所有節(jié)點(diǎn)。比如說(shuō)“Cherry”這個(gè)節(jié)點(diǎn)（4-5）

SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;

• 增加節(jié)點(diǎn)
  我們想添加“Strawberry“到”Red“節(jié)點(diǎn)下，那么“Red”節(jié)點(diǎn)的右數(shù)就得從6到8，而“Yellow”就得從7-10變成9-12，以此類(lèi)推。更新Red節(jié)點(diǎn)就意味著大于5的左數(shù)和右數(shù)都要增加2。

UPDATE tree SET rgt=rgt+2 WHERE rgt>5;
UPDATE tree SET lft=lft+2 WHERE lft>5;

INSERT INTO tree SET lft=6, rgt=7, title='Strawberry';

• 優(yōu)點(diǎn)
  查詢(xún)的時(shí)候只需要一條SQL語(yǔ)句

2 進(jìn)入正題

• Mysql架構(gòu)
  • Parser
    將用戶的查詢(xún)語(yǔ)句進(jìn)行解析，并創(chuàng)建一個(gè)內(nèi)部的數(shù)據(jù)結(jié)構(gòu)——分析樹(shù)
  • Optimizer
    各種優(yōu)化，例如重寫(xiě)查詢(xún)、選擇讀取表的順序，以及使用哪個(gè)索引等。

• 類(lèi)目表結(jié)構(gòu)(是否可以改進(jìn)?)

CREATE TABLE `itemcats` (
  `cid` int(11) NOT NULL,
  `parent_cid` int(11) DEFAULT NULL,
  `name` varchar(50) NOT NULL,
  `is_parent` tinyint(1) NOT NULL,
  `status` varchar(20) DEFAULT NULL,
  `sort_order` int(11) DEFAULT NULL,
  `lft` int(11) NOT NULL,
  `rght` int(11) NOT NULL,
  `level` int(11) NOT NULL,
  PRIMARY KEY (`cid`),
  KEY `parent_cid` (`parent_cid`),
  KEY `lft_rght` (`lft`,`rght`),
  KEY `level` (`level`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

• 為什么InnoDB表要建議用自增列做主鍵?
  如果InnoDB表的數(shù)據(jù)寫(xiě)入順序能和B+樹(shù)索引的葉子節(jié)點(diǎn)順序一致的話，這時(shí)候存取效率是最高的
  • 使用自增列(INT/BIGINT類(lèi)型)做主鍵，這時(shí)候?qū)懭腠樞蚴亲栽龅?，和B+數(shù)葉子節(jié)點(diǎn)分裂順序一致；
  • 如果一個(gè)InnoDB表又沒(méi)有顯示主鍵，又有可以被選擇為主鍵的唯一索引，但該唯一索引可能不是遞增關(guān)系時(shí)(例如字符串、UUID、多字段聯(lián)合唯一索引的情況)，該表的存取效率就會(huì)比較差。

• 數(shù)值類(lèi)型

• 字符串類(lèi)型
  • char（n）和varchar（n）中括號(hào)中n代表字符的個(gè)數(shù)，并不代表字節(jié)個(gè)數(shù)，所以當(dāng)使用了中文的時(shí)候(UTF8)意味著可以插入m個(gè)中文，但是實(shí)際會(huì)占用m*3個(gè)字節(jié)。
  • 同時(shí)char和varchar最大的區(qū)別就在于char不管實(shí)際value都會(huì)占用n個(gè)字符的空間，而varchar只會(huì)占用實(shí)際字符應(yīng)該占用的空間+1，并且實(shí)際空間+1<=n。
  • 超過(guò)char和varchar的n設(shè)置后，字符串會(huì)被截?cái)唷?/li>
  • char在存儲(chǔ)的時(shí)候會(huì)截?cái)辔膊康目崭?，varchar和text不會(huì)。
  • varchar會(huì)使用1-3個(gè)字節(jié)來(lái)存儲(chǔ)長(zhǎng)度，text不會(huì)。