MySQL数据库，详解索引原理(四)

b+树

先看个b+树结构图：

b+树的特征

1. 每个结点⾄多有m个⼦⼥

2. 除根结点外,每个结点⾄少有[m/2]个⼦⼥，根结点⾄少有两个⼦⼥

3. 有k个⼦⼥的结点必有k个关键字

4. ⽗节点中持有访问⼦节点的指针

5. ⽗节点的关键字在⼦节点中都存在（如上⾯的1/20/35在每层都存在），要么是最⼩值，要么是最⼤值，如果节点中关键字是升序的⽅式，⽗节点的关键字是⼦节点的最⼩值

6. 最底层的节点是叶⼦节点

7. 除叶⼦节点之外，其他节点不保存数据，只保存关键字和指针8. 叶⼦节点包含了所有数据的关键字以及data，叶⼦节点之间⽤链表连接起来，可以⾮

常⽅便的⽀持范围查找b+树与b-树的⼏点不同

1. b+树中⼀个节点如果有k个关键字，最多可以包含k个⼦节点（k个关键字对应k个指针）；⽽b-树对应k+1个⼦节点（多了⼀个指向⼦节点的指针）

2. b+树除叶⼦节点之外其他节点值存储关键字和指向⼦节点的指针，⽽b-树还存储了数据，这样同样⼤⼩情况下，b+树可以存储更多的关键字

3. b+树叶⼦节点中存储了所有关键字及data，并且多个节点⽤链表连接，从上图中看⼦节点中数据从左向右是有序的，这样快速可以⽀撑范围查找（先定位范围的最⼤值和

最⼩值，然后⼦节点中依靠链表遍历范围数据）

B-Tree和B+Tree该如何选择？

1. B-Tree因为⾮叶⼦结点也保存具体数据，所以在查找某个关键字的时候找到即可返回。⽽B+Tree所有的数据都在叶⼦结点，每次查找都得到叶⼦结点。所以在同样⾼度的B-Tree和B+Tree中，B-Tree查找某个关键字的效率更⾼。

2. 由于B+Tree所有的数据都在叶⼦结点，并且结点之间有指针连接，在找⼤于某个关键字或者⼩于某个关键字的数据的时候，B+Tree只需要找到该关键字然后沿着链表遍历就可以了，⽽B-Tree还需要遍历该关键字结点的根结点去搜索。

3. 由于B-Tree的每个结点（这⾥的结点可以理解为⼀个数据页）都存储主键+实际数据，⽽B+Tree⾮叶⼦结点只存储关键字信息，⽽每个页的⼤⼩有限是有限的，所以同⼀页能存储的B-Tree的数据会⽐B+Tree存储的更少。这样同样总量的数据，B-Tree的深度会更⼤，增⼤查询时的磁盘I/O次数，进⽽影响查询效率。Mysql的存储引擎和索引mysql内部索引是由不同的引擎实现的，主要说⼀下InnoDB和MyISAM这两种引擎中的索引，这两种引擎中的索引都是使⽤b+树的结构来存储的。

InnoDB中的索引

Innodb中有2种索引：主键索引（聚集索引）、辅助索引（⾮聚集索引）。

主键索引：每个表只有⼀个主键索引，b+树结构，叶⼦节点同时保存了主键的值也数据记录，其他节点只存储主键的值。

辅助索引：每个表可以有多个，b+树结构，叶⼦节点保存了索引字段的值以及主键的值，其他节点只存储索引指端的值。

MyISAM引擎中的索引

B+树结构，MyISM使⽤的是⾮聚簇索引，⾮聚簇索引的两棵B+树看上去没什么不同，节点的结构完全⼀致只是存储的内容不同⽽已，主键索引B+树的节点存储了主键，辅助键索引B+树存储了辅助键。表数据存储在独⽴的地⽅，这两颗B+树的叶⼦节点都使⽤⼀个地址指向真正的表数据，对于表数据来说，这两个键没有任何差别。由于索引树是独⽴的，通过辅助键检索⽆需访问主键的索引树。

如下图：为了更形象说明这两种索引的区别，我们假想⼀个表存储了4⾏数据。其中Id作为主索引，Name作为辅助索引，图中清晰的显⽰了聚簇索引和⾮聚簇索引的差异。