B+树以及非聚簇索引和聚簇索引

1 B树以及B+树

1.1 B树

是一种多路搜索树，假设为M叉树
1. 每个节点中的关键字，比指向儿子的指针少一，即每个节点最多有M-1个关键字和M个指针
2. 关键字集合分布在整棵树中，任何一个关键字出现且只出现在一个节点中，即是说，有可能在非叶子节点命中。

1.2 B+树

B+树是B树的变种，也是一种多路搜索树，假设为M叉树
1. 每个节点的关键字个数和指向儿子的指针树最多一样，即每个节点最多有M个关键字和M个指针。
2. 所有关键字都会在叶子节点出现，所以不可能在非叶子节点命中。

1.3 MySQL索引采用B+/B树原因

从上面1.1 ， 1.2可知，不管是B树，还是B树，其形状都是“矮胖”型的，而红黑树或是AVL树，都是“高瘦”型。
上面这两种形状的树，如果在内存中查找时，不会有什么问题。但是，如果现在数据是在磁盘，每次查找都要将磁盘中的数据加载内存中。一般来讲，访问一个节点，就要访问一次磁盘。
由上可知，“矮胖”型的，到命中时，访问的节点要更少，也就是更少的访问磁盘，所以，“矮胖”型更加高效，更适合做索引。

2 非聚簇索引和聚簇索引

2.1 非聚簇索引

非聚簇索引就是说，叶子节点只是存着数据的地址，而不是数据本身。索引文件和数据文件两个文件是分开的。MyISAM就是采用非聚簇索引。

非聚簇索引的主键索引和二级索引是什么区别的，上面图为主键索引，再来一个二级索引。

查找时，从上到下找到叶子节点，叶子节点保存着数据的地址，拿到这个地址后，就可以直接到磁盘中找了。

2.2 聚簇索引

聚簇索引的叶子节点中保存着数据，InnoDB就是用聚簇索引的。
其主索引如下：

而在聚簇索引的二级索引中，叶子节点保存着主键，所以在二级索引中查找时，先找到二级索引中的主键，在根据这个主键，从聚簇索引中找到该主键的数据，所以需要两次查找。