本文目录一览：
MySQL BTREE索引
个人能力有限，如有错误请指出，共同学习。
二叉树
B树
B+树
特点：
聚簇索引
二级索引
key数据存储量估算：
若每个页可以存1000个key，而且树的高度是4，那么
前提条件如下：
插入步骤
步骤一
因为索引中还没有数据，所以此时的B+树只有一个空的根结点，又由于一个页只能存3个key，首先将10，20，5插入进去（实际上此步发生了3次插入），然后在页面内做数据排序，最终结果如下图：
步骤二：
由于根页面已经写满，此时插入8，将发生分裂（根页面分裂），大致步骤如下：
注意：在分裂过程中，根结点始终是不会变的，不管变成多大的树，根结点的页面号始终如一。
步骤五：
插入数据40，发现比根结点23大，找到103号页面，发现已满，执行分裂，分裂同上面叶子结点的分裂步骤。分裂后如图所示：
步骤六：
继续插入下一个数据9，因为比20小，找到101号页面，发现已满，需要做叶子结点分裂，如下图：
传统B+树的数据删除，一般都会有一个所谓的填充因子，来控制页面数据的删除比例，如果数据量小于这个填充因子所表示的数据量，就会有节点合并，这与分裂是相对应的。
InnoDB的实现与传统B+树算法有不同之处，InnoDB在删除索引数据时，会先检查当前页剩余的记录数，如果只剩下一条记录，就会直接将这个页面从B+树中摘除，也只有这种情况，InnoDB才会回收一个页面，InnoDB的页面没有合并一说，但是对于根节点，即使索引数据全部删除，根节点页依然存在，只不过是以空页的形式存在。
下面举个例子描述索引删除过程，前提条件与前面插入记录时一致。
删除数据 50
删除过程全部结束，最终得到一个空的索引页。
《MySQL运维内参》
B+树动画演示：
mysql btree和hash索引对比
只有 MEMORY 存储引擎的表才可以选择使用 BTREE 索引或者 HASH 索引，像我们 常用的innodb只支持btree索引 。两种不同类型的索引各有其不同的适用范围。
Hash索引只能用于对等比较，例如=,=（相当于=）操作符。时间复杂度是O(1)，一次查找便能定位数据，不像BTree索引需要从根节点到枝节点，最后才能访问到页节点这样多次IO访问，所以Hash在 单值查询 下检索效率远高于BTree索引。
但是，事实上我们更多情况是使用btree而不是hash
HASH 索引有一些重要的特征需要在使用的时候特别注意，如下所示。
下面我们可以进行验证：
创建一个city_memory表，其中 country_id字段上加了 HASH索引
插入数据
1、先开看这条等值条件sql
2、那么再来看 大于和小于条件sql
3、那么in这种范围条件呢？
in 条件对于hash来说是支持的，同样btree当然也支持。而且btree索引在使用in条件找数据时相对于hash性能更好，因为rows由4变为2（说明使用btree扫描2行即可找到）证明如下：
4、 BETWEEN .. AND .. 条件呢？
BETWEEN .. AND .. 条件在 不会用到hash索引！再来看看 btree的情况：
BETWEEN .. AND .. 条件能够使用到btree索引。
5、like 条件呢？
为了使用like条件，我们先将country_id类型改为 varchar
我们再来执行：
like条件会让hash索引失效。我们再来看btree下的like怎样：
好的，btree下也支持 like的不带开头%的访问查询
1、先来看hash索引支不支持排序
hash索引果然不能用在排序中，这多么致命呀！产生了 Using filesort文件内排序。性能上是个大坑。
2、同样，我们知道分组是要基于排序的。排序不使用索引，分组当然也不使用索引了。验证如下：
最终不仅没使用到索引，还产生了文件内排序和使用临时表。
当使用 MEMORY 引擎表的时候，如果是默认创建的 HASH索引，就要注意 SQL 语句的编写，确保可以使用上索引，如果索引字段需要 范围查询、排序、分组 就请使用btree索引；
mysql中的索引怎样使用btree索引
B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型，除了 Archive 存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL 中是如此，实际上在其他的很多数据库管理系统中B-Tree 索引也同样是作为最主要的索引类型，这主要是因为 B-Tree 索引的存储结构在数据库的数据检 索中有非常优异的表现。
一般来说， MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree 的结构来存储的，也就是所有实际需要的数据都存放于 Tree 的 Leaf Node ，而且到任何一个 Leaf Node 的最短路径的长度都是完全相同的，所以我们大家都称之为 B-Tree 索引当然，可能各种数据库（或 MySQL 的各种存储引擎）在存放自己的 B-Tree 索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree 索引实际使用的存储结构实际上是 B+Tree ，也就是在 B-Tree 数据结构的基础上做了很小的改造，在每一个
Leaf Node 上面出了存放索引键的相关信息之外，还存储了指向与该 Leaf Node 相邻的后一个 LeafNode 的指针信息，这主要是为了加快检索多个相邻 Leaf Node 的效率考虑。
在 Innodb 存储引擎中，存在两种不同形式的索引，一种是 Cluster 形式的主键索引（ Primary Key ），另外一种则是和其他存储引擎（如 MyISAM 存储引擎）存放形式基本相同的普通 B-Tree 索引，这种索引在 Innodb 存储引擎中被称为 Secondary Index 。
