Mysql中的B+tree索引

BTree意思是多路平衡查找树，它是一种数据结构。MySQL的InnoDB和MyISAM存储引擎，都是使用它来存储索引。BTree可细分为B-Tree和B+Tree，B+Tree是B-Tree的升级版。MySQL的InnoDB和MyISAM存储引擎使用的是B+Tree

一 B-Tree

先来了解一下B-Tree,学名：多路平衡查找树，是为磁盘等外存储设备设计的一种平衡查找树，

为了描述B-Tree，首先定义一条记录为一个二元组[key, data] ，key为记录的键值，对应表中的主键值，data为一行记录中除主键外的数据。对于不同的记录，key值互不相同。如下图中的紫色部分就是key，橙色部分就是一行数据，绿色部分就是指针。

 对于B-Tree的查找，从图中可以看到，单个查找应该还可以，但是如果做范围查找的话，存在回旋查询的问题。同样order by排序的时候效率也很低，因为要把树上的数据手动排序一遍

二 B+Tree

B+Tree的数据都是保存在叶子节点，非叶子节点只存储key,不存储data,并且所有的叶子节点是一个链表结构，这样有利于范围查找。

三 聚簇索引于非聚簇索引

聚簇索引：将数据与索引放到了一块，索引的叶子节点保存了行数据

非聚簇索引：将数据分开存储，索引结构的叶子节点指向了数据对应的位置

通常，主键都是聚簇索引，我们根据实际情况自行添加的索引都是辅助索引，辅助索引就是一个为了需找主键索引的二级索引，先得找到主键索引再通过主键索引找数据（这就是所谓的回表）

聚簇索引的优点是对于主键的排序查找和范围查找速度非常快，缺点也很明显：1插入速度眼中依赖于插入顺序，按照主键的顺序插入是最快的方式，否则会出现页分裂，严重影响性能。因此，对于Innodb表，我们都会定义一个自增的ID列作为主键。2 更新主键的代价很高，因为将会导致被更新的行移动，一次，一般定义主键不可更新。3 二级索引访问需要两次索引查找，第一次找到主键值，第二次根据主键值找到行数据。