个人能力有限，如有错误请指出，共同学习。
广灵网站建设公司成都创新互联公司,广灵网站设计制作，有大型网站制作公司丰富经验。已为广灵上千家提供企业网站建设服务。企业网站搭建\外贸网站制作要多少钱，请找那个售后服务好的广灵做网站的公司定做！
二叉树
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索引的原理和数据结构有助于我们更好的使用索引以及进行SQL优化，索引是在存储引擎层面实现的，所以不同的引擎实现的索引也有一定的区别，但是在生产环境中，我们最常用的就是InnoDB引擎和B树索引，OK，那本文要讨论的重点也同样是 InnoDB引擎下的B树索引 。
我们建立一个表来进行测试，表的DDL如下所示，我们要关注的是表t_book上的主键索引id和name author publish_date三列组成的索引test_index。
Mysql中的B树索引是使用B+树实现的，关于B+树的数据结构个人认为美团点评技术博客中Mysql索引原理及慢查询优化一文中介绍的非常详实，B+树的数据结构如下图所示。
图中浅蓝色块即磁盘块，根节点磁盘块中存储17和35两个数据，其中指针P1指向小于17的数据，指针P2指向大于17小于35的数据，指针P3指向大于35的数据。显然通过B+树索引查询数据与B+树的高度有关，如上图的B+树索引查找一个叶子节点的数据只需要三次磁盘IO，对于Mysql来说三层的B+树可以索引上百万的数据，这对于查询效率的提升是巨大的。
总结起来Mysql中B树索引有以下关键特点：
Mysql中的B树索引有两种数据存储形式，一种为聚簇索引，一种为二级索引。
InnoDB一般会使用表的主键来作为聚簇索引，如果一个表没有主键（不建议这么玩）InnoDB会选用一个唯一非空索引来代替，如果没有这样的索引，InnoDB会隐式建立一个聚簇索引。聚簇的含义即是数据行和相邻的键值紧凑的存储在一起，占据一块连续的磁盘空间，因此通过聚簇索引访问数据可以有效减少随机IO，通常使用聚簇索引查找比非聚簇索引查找速度更快。以我们建立的表t_book为例，聚簇索引即为自增主键id，其B树索引数据结构可以用下图来表示。
聚簇索引有以下关键特点：
InnoDB的B树索引中除了聚簇索引，就都是二级索引了，二级索引的含义是索引的叶子节点除了存储了索引值，还存储了主键id，在使用二级索引进行查询时，查找到二级索引B树上的叶子节点后还需要去聚簇索引上去查询真实数据，但是这里有一种特殊情况，即查询所需的所有字段在二级索引中都可以获取，此时就不需要再去回表查数据了，这种情况就是索引覆盖（EXPLAIN中EXTRA列中会出现USING INDEX，本文只关注索引结构，不详细讨论索引覆盖等技术的使用，如果深入理解索引的数据结构，索引覆盖等技术也没有那么神秘）。
在我们的测试表t_book中，test_index即为二级索引，由于我们把除了主键id所有的列都作为一个联合索引，所以在这个表上的查询都可以使用索引覆盖技术，但是具体生产环境中也不建议总是采用这种做法，索引列的增加也会增大插入更新数据时的索引更新成本，具体的优化要视具体情况决策。t_book上的二级索引test_index的索引结构由下图表示。
通过以上结构，我们可以推断出二级索引的以下关键特点：
索引覆盖：
最左前缀匹配：
二级索引可以说是我们在Mysql中最常用的索引，通过理解二级索引的索引结构可以更容易理解二级索引的特性和使用。
最后聊点轻松的索引结构，哈希索引就是通过哈希表实现的索引，即通过被索引的列计算出哈希值，并指向被索引的记录。
哈希索引有如下特性：
Mysql索引原理及慢查询优化
高性能Mysql 第三版
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 。
事实上，在MySQL数据库中，诸多存储引擎使用的是B+树，即便其名字看上去是BTREE。
4.1 innodb的索引机制
先以innodb存储引擎为例，说明innodb引擎是如何利用B+树建立索引的
首先创建一张表：zodiac，并插入一些数据
对于innodb来说，只有一个数据文件，这个数据文件本身就是用B+树形式组织，B+树每个节点的关键字就是表的主键，因此innode的数据文件本身就是主索引文件，如下图所示，主索引中的叶子页（leaf page）包含了数据记录，但非叶子节点只包含了主键，术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起，因此这种索引被称为聚簇索引，或聚集索引。
这种索引方式，可以提高数据访问的速度，因为索引和数据是保存在同一棵B树之中，从聚簇索引中获取数据通常比在非聚簇索引中要来得快。
所以可以说，innodb的数据文件是依靠主键组织起来的，这也就是为什么innodb引擎下创建的表，必须指定主键的原因，如果没有显式指定主键，innodb引擎仍然会对该表隐式地定义一个主键作为聚簇索引。
同样innodb的辅助索引，如下图所示，假设这些字符是按照生肖的顺序排列的（其实我也不知道具体怎么实现，不要在意这些细节，就是举个例子），其叶子节点中也包含了记录的主键，因此innodb引擎在查询辅助索引的时候会查询两次，首先通过辅助索引得到主键值，然后再查询主索引，略微有点啰嗦
MySQL的Innodb存储引擎的索引分为聚集索引和非聚集索引两大类
特点：B+树叶子节点存储行数据
一个表中，必须有一个聚集索引，只能有一个聚集索引，Innodb通常把一个表的主键索引作为聚集索引，如果没有主键InnoDB会选择一个唯一索引代替。如果没有这样的索引，InnoDB会隐式的定义一个主键来作为聚集索引，这个字段为6个字节，类型为长整形。
利用主键索引查找行数据是最快的，建议使用自增主键原因是利于索引树的构建（主键自增写入时新插入的数据不会影响到原有页，插入效率高；但是如果主键是无序的或者随机的，那每次的插入可能会导致原有页频繁的分裂，影响插入效率）
特点：B+树叶子节点存储主键ID
一个表中可以有多个非聚集索引，每个非聚集索引即是一棵B+树
通过非聚集索引查找数据时，需要先在非聚集索引上找到主键ID，再从聚集索引获取行数据，这个过程就称之为回表
B树索引中的B树实际上是B+树，至于为什么使用B+树而不使用B树或者红黑树的原因在另外的文章中有提及。
特点：
特点：类似JDK中的HashMap，但无法支持范围查询
特点：使用的算法仍然是B树索引，不同的就是索引列的值必须唯一
对于普通索引来说，查找到满足条件的第一个记录后，需要查找下一个记录，直到碰到第一个不满足条件的记录。
对于唯一索引来说，由于索引定义了唯一性，查找到第一个满足条件的记录后，就会停止继续检索，提升索引性能
另外插入行时会构建该唯一索引，假如索引值重复将插入失败，适合业务上做唯一性检验
通过建立倒排索引，可以极大的提升检索效率,解决判断字段是否包含的问题，但是业务上一般都不采用这种索引，而是使用ES处理全文搜索需求
仅对某个特定字段建立的索引，如(biz_id)
对多个字段建立的索引，如(biz_id,type)