前言

B+树，相信在学习资料库时，多多少少都会听过，如同二元树、平衡二元树等，他就是一种资料结构，定义十分複杂，在这里只会简单对B+树做个简介。

何谓B+树

是一种资料结构，在 B+树中所有纪录结点都是按照键值大小顺序放在同一层的叶子结点上(leaf node)，各叶子结点会用 pointer 连结，可以从一个叶子结点到下一个叶子结点，这个好处是找到资料后可以很快再移动到下一个资料就不需要每次都从 root 出发，如图1：是一颗高度=2 的 B+ 树。

图1 参考至书籍-MySQL 技术内幕 InnoDB 存储引擎
这里可以看到两个部分

Index Page: B+树中的非叶子结点Leaf page: B+树中的叶子结点

B+树索引

前面是简单说一下一颗 B+树的长相，但是 B+树在资料库中的实现就是B+树索引，又可以分成

丛集索引 clustered index辅助索引 secondary index

这两种索引都是 B+树。

丛集索引 clustered index

上一篇文章有说过，在 InnoDB 中，每一张表都是索引组织表，可以回去看一下MySQL 系列文 - 索引的相关知识 - 索引组织表，也就是说每张 TABLE 都是依照 PK 顺序存放，而这里说的丛集索引，就是依照每张 TABLE 的 PK 顺序建立的一颗 B+树，叶子结点的部分就是放所有的资料，简单来说

丛集索引上的叶子结点(leaf node)就是放所有的资料，又称资料页。由于一张 TABLE 里的资料只能按照一个 B+树来排序，因此每张 TABLE 只会有一个丛集索引。

当我们在SELECT 资料时，如果优化器决定使用丛集索引，那么就可以在丛集索引的叶子结点上直接找到资料。如果查的是範围资料例如SELECT * FROM table_name WHERE id>10 and id <20 也能快速找到这个範围，因为资料都已经依照 PK 去排序了。

★ 範例

假设有一张表: tel_tb
PK: id
id|name|phone_num
----|-------------
2|Amy|0912345678
5|Simon|0912876543
8|Terry|0912222222
9|Bob|0912111111

结构如下

图2

现在有一个语法 SELECT * FROM tel_tb WHERE id = 5 其查找流程如下
找到叶子结点，资料就在叶子结点上。

图3

辅助索引 secondary index

又称为非丛集索引，跟丛集索引不同的是，其叶子结点不包含每一笔资料的所有资料。这里的叶子结点放的是两个部分

建立此 index 假设是用 name，那么叶子结点会放 name另一个是储存对应的丛集索引，称作书籤(bookmark)，告诉 InnoDB 要去哪里可以找到真正的资料
假设现在要透过辅助索引(secondary index) 来找资料，顺序如下透过辅助索引找到对应的叶子结点获得对应丛集索引的 PK透过丛集索引找到完整的资料

★ 範例

同上面的範例
假设有一张表: tel_tb
PK: id
id|name|phone_num
----|-------------
2|Amy|0912345678
5|Simon|0912876543
8|Terry|0912222222
9|Bob|0912111111
现在另外建立一个辅助索引在 name 栏位
CREATE INDEX index_name ON tel_tb (name)
结构如下

图4
从图中可以知道，每建立一个辅助索引，就会在建立一个 B+树，所以表的空间会占用 Disk 更多，此外注意看辅助索引的叶子结点，并不是真实资料，放的是索引结点，也就是 name 栏位的值，而资料区域放的是对应的PK。

现在有一个语法 SELECT * FROM tel_tb name = 'Bob' 其查找流程如下
先找辅助索引找到对应的PK是 9 ，再到丛集索引去找到 9 所对应的真实资料。

图5

---

小结

这篇主要在讲丛集索引与辅助索引的差异，以及当我们在下 SELECT 语法时，怎么在 InnoDB 里面去查找，其实有一些状况是不会到丛集索引里面去拿资料的，这个观念会在下一篇跟大家说明。

资料库知识相当广泛，文中若有不正确的地方，也烦请各位大神不吝指教，谢谢

---