1 如何在数据库中存储层级结构
(1) 邻接表模型
求节点的路径
举例来说，“Cherry”所在的路径为Food > Fruit > Red > Cherry。在这里，我们可以从Cherry开始查起，然后递归查询查询节点前的节点，直到某节点的父节点ID为0(Food)。优点
简单易懂缺点
执行起来效率低下。我们对于每个结果，期望只需要一次查询；可是当使用邻接表模型时嵌套的递归使用了多次查询，当树很大的时候，这种慢就会表现得尤为明显。
上帝是公平的，当在执行时效率低下，意味着可以增加预处理的程度。
(2）MPTT(修改过的前序遍历算法)
- 原理
现在我们把树“横”着放。如下图所示，我们首先从根节点（“Food”）开始，先在它左侧标记“1”，然后我们到“Fruit”，左侧标记“2”，接着按照前序遍历的顺序遍历完树，依次在每个节点的左右侧标记数字。
- 实现
- 打印树
如果要想打印树，你只需要知道你要检索的节点。比如，想要打印“Fruit”的子树，可以查询左数大于2而小于11的节点。
SELECT * FROM tree WHERE lft BETWEEN 2 AND 11;
- 求节点的路径
对于某节点，我们只需求出左数值小于其左数值、右数大于其右数的所有节点。比如说“Cherry”这个节点（4-5）
SELECT title FROM tree WHERE lft < 4 AND rgt > 5 ORDER BY lft ASC;
- 增加节点
我们想添加“Strawberry“到”Red“节点下，那么“Red”节点的右数就得从6到8，而“Yellow”就得从7-10变成9-12，以此类推。更新Red节点就意味着大于5的左数和右数都要增加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';
- 优点
查询的时候只需要一条SQL语句
2 进入正题
- Mysql架构
- Parser
将用户的查询语句进行解析，并创建一个内部的数据结构——分析树 - Optimizer
各种优化，例如重写查询、选择读取表的顺序，以及使用哪个索引等。
- Parser
- 类目表结构(是否可以改进?)
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表的数据写入顺序能和B+树索引的叶子节点顺序一致的话，这时候存取效率是最高的- 使用自增列(INT/BIGINT类型)做主键，这时候写入顺序是自增的，和B+数叶子节点分裂顺序一致；
- 如果一个InnoDB表又没有显示主键，又有可以被选择为主键的唯一索引，但该唯一索引可能不是递增关系时(例如字符串、UUID、多字段联合唯一索引的情况)，该表的存取效率就会比较差。
- 数值类型
- 字符串类型
- char（n）和varchar（n）中括号中n代表字符的个数，并不代表字节个数，所以当使用了中文的时候(UTF8)意味着可以插入m个中文，但是实际会占用m*3个字节。
- 同时char和varchar最大的区别就在于char不管实际value都会占用n个字符的空间，而varchar只会占用实际字符应该占用的空间+1，并且实际空间+1<=n。
- 超过char和varchar的n设置后，字符串会被截断。
- char在存储的时候会截断尾部的空格，varchar和text不会。
- varchar会使用1-3个字节来存储长度，text不会。
