索引是什么，下边是mysql的官方网界定：
“数据库索引是协助mysql高效率读取数据的排好序的算法设计”。 抓重点，数据库索引的实质是一种算法设计,并且是排好序的。数据库索引功效有2个，一个是排列，一个是迅速搜索，而迅速搜索的基本便是排好啦序的数据库索引。
那麼数据库索引能够有什么算法设计：
二叉树、红黑树、hash表和B-Tree
二叉树数据库索引
下边大家以二叉树这类算法设计的数据库索引为例子，表明数据库索引是怎样工作中的：
倘若现在有一张表，表里边有两个字段名 Col1 和 Col2：
如今我查看一个sql： select * from t where col2=89;
不在应用数据库索引状况下，mysql会从头开始解析xml表t，一条条的向下查看，并核对 col2 字段名是不是为89。
假如应用了二叉树数据库索引，在对col2字段名创建数据库索引的情况下，mysql会将col2字段名的全部內容以二叉树的算法设计载入到一个数据库索引文档中。
我们知道二叉树实际上是由链表形变而成的，是由好几个连接点和连接偏向组成的。在二叉树数据库索引中，每一个连接点都储存着key和value，key是几乎col2的值（89），value是col2这一字段名所属行的硬盘详细地址（0x07,0x56这类的）。
二叉树的特性便是一个连接点的右子连接点的key比左子连接点的key大，根据二叉树开展搜索的算法复杂度是 O(log2n)，而无需二叉树根据解析xml的方法搜索的复杂性是 O(n)。因此 在二叉树中能够迅速寻找 key 为 89 的连接点，获得到这一连接点的value（储存col2 = 89的行所属的储存空间详细地址），随后再从这一详细地址中获得col2=89这一行的全部字段名的数据信息。
树枝的每一个数据库索引连接点都被分派一个储存空间详细地址，换句话说一棵树的全部连接点全是存有一块硬盘上的不一样部位。每一个父节点都是有两根单边连接偏向上下子连接点，单边连接储存着子连接点的硬盘详细地址。父节点A能够根据单边连接上纪录的硬盘详细地址寻找子连接点B的部位。
搜索一个数据库索引的情况下必须将树的连接点中的数据信息从硬盘载入到运行内存，这便会产生一次硬盘IO实际操作。假如这一连接点的key并不是我想找的数据库索引值，便会依据单边连接中存的硬盘详细地址寻找子连接点的储存空间，载入到运行内存，这也是一次IO实际操作。
因而，从根节点每向下找一层子连接点便是一次IO实际操作。
假如二叉树这类算法设计是按字段名值由小到大或是从大到小的次序来搭建得话,便会彻底衰退为一个单向链表，复杂性就又变成了O(n)，和全表扫描仪一行行解析xml没有什么差别。
比如，对图中中的col1这一字段名创建二叉树数据库索引便会产生这类状况。
结果：二叉树搭建数据库索引很有可能会衰退为一个贴近单向链表的构造，这时搜索和排列的复杂性与全表扫描仪没什么差别。因而二叉树不宜做为数据库索引的算法设计
红黑树数据库索引
红黑树的实质是一个二叉平衡树。红黑树每加上一个连接点（比如是连接点A）会查验该连接点A上下两侧的子支系是不是均衡，假如该连接点A的右侧的等级超过该连接点左侧的等级超出2层，便会做一个连接点的均衡（左旋体），促使该连接点A连接点的上下两侧的叠加层数相同。
而红黑树的全自动均衡作用能够处理二叉树衰退为单向链表的难题
之上图上col1字段名建立红黑树数据库索引为例子：
红黑树的复杂性也是 O(log2n)，它的特性是加上或是删掉连接点的情况下会全自动均衡。
可是，用红黑树做为mysql数据分析表的数据库索引還是存在的问题的。
你回过头来一个几百万的表用红黑树搭建数据库索引，这棵树便会有好多好多层，由于红黑树终究是一个二叉树，每一个连接点只有有两个分岔，因此 数据信息一多，树的等级就多。当搜索一个key较为大的数据信息时，就需要从根节点一直寻找最底层叶连接点，高效率還是不高。当数据分析表中的纪录数越多，红黑树的等级越高，查看高效率就越低。
举个事例，用红黑树搭建一个有100多万元数据信息的表的数据库索引，那麼这一红黑树大约有20层。假如我搜索的数据信息恰好在叶子节点，代表着我想在红黑树上查20个连接点才可以寻找最底层。
每往下一层去解析xml一个连接点便是一次IO实际操作，便会产生20次磁盘io。
因此 红黑树的短板取决于叠加层数很有可能过多。大家期待可以在创建上百万的数据库索引的基本上把树的等级操纵在3~4层以内。
结果：红黑树构 建数据库索引的短板取决于储存大表数据库索引时，树等级过多，造成搜索产生的io频次多。
B-Tree数据库索引（多叉平衡树）
B-Tree在红黑树的基本上选用了 横着拓展的提升。一般二叉树和红黑树的一个连接点只有存一个数据库索引（一个连接点的储存空间只存一个key-value数据信息），而B-Tree的每一个连接点能够储存好几个数据库索引（给一个连接点分派一个大一些的储存空间存好几个key-value数据信息）。因此 B-Tree的每一个连接点能够有好几个单边连接。
下面大家看一下一个维持在3层的B-Tree的搭建全过程
B Tree的特性
1. 全部的叶子节点的等级全是一样的且叶连接点从左往右key是安排好序的是增长的，比如上边 全部叶子节点全是在第三层。
2. B树的每一个连接点尽管有好几个连接偏向，可是每一个数据库索引還是仅有2个连接偏向，每一个数据库索引组成的子树都考虑二叉树的特点（右子连接点比左子连接点的key大）。
3. 单独连接点内的好几个数据库索引是增长的有排列的。当往B树中插进一个数据库索引的情况下，数据库索引被插进到一个连接点会在这个连接点中合别的数据库索引开展排列排序。
结果：B树的横着拓展特点就很好的解决了红黑树叠加层数过高的难题，但mysql還是沒有挑选B树做为数据库索引的数据信息結果，缘故是B树没法高效率的保证范畴搜索。
B Tree数据库索引
B 树合乎B Tree的全部特点。可是B Tree 的非叶子节点不储存value，只储存key（key便是数据库索引字段名的字段名值，value是该数据库索引字段名相匹配的行的硬盘详细地址或是是数据库索引所属行的别的列的具体数据信息，value存什么叫因储存模块的种类而异的）。这促使每一个非叶子节点能够储放大量的数据库索引（由于不存value节约了室内空间）。
B 树的每一个叶子节点中间维护保养这一个双重连接，这一双重连接储存着邻近叶连接点的储存空间详细地址，促使邻近的叶连接点能够寻找另一方的硬盘地理位置。
叶子节点会包括全部的数据库索引字段名的key和value。一部分子连接点的key会沉余储存一份在父节点中。
B 树的一个连接点在硬盘中主要表现为一个数据信息页，在加上或是删掉行的情况下造成的连接点均衡（页瓦解）。
一个连接点中的每一个数据库索引的两根连接表针储存着他的儿子连接点的硬盘详细地址。
B 树的结构如下图
B 树的搜索也是以根节点逐渐向下查。以搜索图中中的53为例子：
B Tree 的根节点是立即存有运行内存中的，因此 第一个连接点不用从硬盘读到运行内存。Mysql根据一定的优化算法（例如二分查找）得到53在50和66这两个数据库索引中间，因此获得50和66中间的单边连接，这一连接储存着根节点的一个子连接点的储存空间详细地址。因此依据这一详细地址从硬盘中载入[52 66]这一子连接点的数据信息到运行内存。在运行内存中开展搜索计算获得53在52和66中间，因此又获得到连接寻找[52 53]这一叶连接点，载入到运行内存，获得53号数据库索引相匹配的value值。
B树和B 树根据横着拓展的方法让树维持一个较为等级，那麼有一个难题：即然树的等级越低，搜索数据库索引的IO实际操作频次越少得话，能不能将全部数据库索引的key-value都放到一个连接点中，那样就仅有1层了？
最先要了解，在树中搜索一个数据库索引的情况下，必须将连接点从硬盘载入到运行内存中。假如上千万个数据库索引都放到一个连接点（大约会出现好几百兆）。一来为了更好地找1个数据库索引而把全部数据库索引的数据加载到运行内存会很消耗运行内存；二来好几百兆的数据信息从硬盘写到运行内存的速率还要很长期。
因此 那样做的高效率很低很笨。
针对mysql来讲，树的一个连接点（不论是叶子节点还是是非非叶子节点）会被分派一个16K的尺寸的页来存好几个数据库索引，一个连接点便是一个数据信息页。
我们可以查询mysql一页有多大
show global status like \"Innodb_page_size\";\n+------------------+-------+\n| Variable_name | Value |\n+------------------+-------+\n| Innodb_page_size | 16384 |\n+------------------+-------+"}">mysql> show global status like "Innodb_page_size";
------------------ -------
| Variable_name | Value |
------------------ -------
| Innodb_page_size | 16384 |
------------------ -------
大家从硬盘取行数据载入到运行内存的情况下，不太可能是以硬盘读一行数据信息到运行内存又再返回硬盘再读一行数据信息到运行内存，那样经常的产生io高效率会很低。因而具体情况是，每一次从硬盘获取数据到运行内存的最小单位是一个页（B 树中一个连接点），因此 有时尽管你只为查一行，可是依然会把一个页给载入到运行内存。
那麼一棵B 树能存多少个数据库索引（是多少条行）呢？
以innodb表的主键数据库索引为例子，一个整形id大约占8B，每一个数据库索引的连接表针占6B，16K/14B = 1170; 因此 一个非叶子节点大约可放1170个数据库索引。而叶子节点储存着value和双重表针，假定value是数据库索引字段名所属行的别的字段名的具体数据信息（假定均值是1K，表针大约占12B，能够忽略），那麼一个叶子节点数最多仅有16个数据库索引。
那麼一棵3层的B Tree，大约能储存 1170*1170*16 = 两千多万 条数据信息。
因此 两千多万条数据信息假如根据B Tree创建数据库索引，要搜索一行数据信息也就开展2次硬盘IO就可以（由于B 树的根节点一般是立即载入在运行内存中的），花的時间也就2次IO的時间。
假如数据信息超出2千多万元，那么就提升 B 树的叠加层数为4层就可以。
Hash表数据库索引
假如以Hash构造做为数据库索引，mysql会创建一个hash表，这一hash表有那样的：先向数据库索引列的值开展一个hash散列函数的测算获得一个散列值，以这一散列值做为key，以数据库索引所属的行数据信息的硬盘详细地址做为value。将key和value存有一个髙速的投射表格中。那样下一次依据数据库索引搜索行的情况下就可以迅速寻找行所属的详细地址。
针对where标准为精确查找（where in/=）而言，hash表的构造比B 树的特性高。可是针对范畴搜索（>/</between）而言，還是要对mysql表开展一行行解析xml，一个个的根据hash函数计算获得散列值， 再根据散列值查hash表的value。
B 树是怎么开展范畴搜索的呢？这全靠B 树叶子连接点中间的双重表针和叶子节点是井然有序的这两个特点。比如作出where id > 30 那样的范畴查看，mysql会先根据B 树的查找算法寻找30所属的叶子节点A，随后根据叶子节点A的双重连接找到它右侧邻近连接点B的详细地址，随后根据B的连接找到B的右侧邻近连接点C的详细地址，一直那样找下来，就获得到 id > 30的数据信息。
充分考虑同是兼具精确查找和范畴搜索mysql還是应用了B 树而无需hash表。
B 树和B树的差别取决于二点：
1. B树的叶子节点中间沒有双重表针，不兼容范畴搜索，假如B树要开展范畴搜索得话务必数次从根节点向下找;
2. B树的非叶子节点包括了value，可是B 树的非叶子节点仅有key沒有value，因为B树的非叶子节点包括value就代表着同样叠加层数的B树和B 树，B树能储存的数据库索引数量远低于B 树。一样是3叠加层数，B 数能够存 1170 * 1170 * 16 = 两千多万个数据库索引，而B树只有存 16*16*16 = 4096个数据库索引。假如用B树形结构存一张两千多万的大表的数据库索引，就必须大约7层。
无论是二叉树，红黑树，B树還是B 树，她们全是对数据信息排好序的结构，排好序的数据库索引是高效率搜索的前提条件。“安排好序”反映在一个连接点的key比左连接点的key大，比右连接点的key小（叶子节点从左往右的key是由小到大的）。这也应了文中的第一句话：“数据库索引是协助mysql高效率读取数据的排好序的算法设计”
