1 如何在數(shù)據(jù)庫中存儲(chǔ)層級(jí)結(jié)構(gòu)
(1) 鄰接表模型
求節(jié)點(diǎn)的路徑
舉例來說煌往,“Cherry”所在的路徑為Food > Fruit > Red > Cherry蜗顽。在這里,我們可以從Cherry開始查起恢筝,然后遞歸查詢查詢節(jié)點(diǎn)前的節(jié)點(diǎn)诞外,直到某節(jié)點(diǎn)的父節(jié)點(diǎn)ID為0(Food)。優(yōu)點(diǎn)
簡單易懂缺點(diǎn)
執(zhí)行起來效率低下府蔗。我們對(duì)于每個(gè)結(jié)果晋控,期望只需要一次查詢;可是當(dāng)使用鄰接表模型時(shí)嵌套的遞歸使用了多次查詢姓赤,當(dāng)樹很大的時(shí)候赡译,這種慢就會(huì)表現(xiàn)得尤為明顯。
上帝是公平的不铆,當(dāng)在執(zhí)行時(shí)效率低下蝌焚,意味著可以增加預(yù)處理的程度。
(2)MPTT(修改過的前序遍歷算法)
- 原理
現(xiàn)在我們把樹“橫”著放狂男。如下圖所示综看,我們首先從根節(jié)點(diǎn)(“Food”)開始,先在它左側(cè)標(biāo)記“1”岖食,然后我們到“Fruit”红碑,左側(cè)標(biāo)記“2”,接著按照前序遍歷的順序遍歷完樹泡垃,依次在每個(gè)節(jié)點(diǎn)的左右側(cè)標(biāo)記數(shù)字析珊。
- 實(shí)現(xiàn)
- 打印樹
如果要想打印樹,你只需要知道你要檢索的節(jié)點(diǎn)蔑穴。比如忠寻,想要打印“Fruit”的子樹,可以查詢左數(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)。比如說“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,以此類推操软。更新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)
查詢的時(shí)候只需要一條SQL語句
2 進(jìn)入正題
- Mysql架構(gòu)
- Parser
將用戶的查詢語句進(jìn)行解析,并創(chuàng)建一個(gè)內(nèi)部的數(shù)據(jù)結(jié)構(gòu)——分析樹 - Optimizer
各種優(yōu)化聂薪,例如重寫查詢家乘、選擇讀取表的順序,以及使用哪個(gè)索引等藏澳。
- Parser
- 類目表結(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ù)寫入順序能和B+樹索引的葉子節(jié)點(diǎn)順序一致的話仁锯,這時(shí)候存取效率是最高的- 使用自增列(INT/BIGINT類型)做主鍵,這時(shí)候?qū)懭腠樞蚴亲栽龅陌试兀虰+數(shù)葉子節(jié)點(diǎn)分裂順序一致扑馁;
- 如果一個(gè)InnoDB表又沒有顯示主鍵,又有可以被選擇為主鍵的唯一索引凉驻,但該唯一索引可能不是遞增關(guān)系時(shí)(例如字符串腻要、UUID、多字段聯(lián)合唯一索引的情況)涝登,該表的存取效率就會(huì)比較差雄家。
- 數(shù)值類型
- 字符串類型
- 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霎俩。
- 超過char和varchar的n設(shè)置后袭厂,字符串會(huì)被截?cái)唷?/li>
- char在存儲(chǔ)的時(shí)候會(huì)截?cái)辔膊康目崭窠P蹋瑅archar和text不會(huì)媳纬。
- varchar會(huì)使用1-3個(gè)字節(jié)來存儲(chǔ)長度,text不會(huì)施掏。