引子
近期入库一批较大数据时候发现有时候查询速度快，而有时候查询速度慢，主要是在使用
like 查询数据时候发现的，%xxx%， xxx% 两个的条件的速度差异很是明显，此问题以前也遇到过，原因就是xxx%时可以命中索引，而 %xxx%时无法命中索引，但此次借此问题有了一些引申思考，数据库的索引方式是什么，如何实现的呢？
一、引申查出 B-Tree 与 hash 两种索引方式，先来看一下他们的特点。
源自：http://dev.mysql.com/doc/refman/5.5/en/index-btree-hash.html。
对于 B-tree 和 hash 数据结构的理解能够有助于预测不同存储引擎下使用不同索引的查询性能的差异，尤其是那些允许你选择 B-tree 或者 hash 索引的内存存储引擎。
B-Tree 索引的特点
B-tree 索引可以用于使用 =, >, >=, <, <= 或者 BETWEEN 运算符的列比较。如果 LIKE 的参数是一个没有以通配符起始的常量字符串的话也可以使用这种索引。比如，以下 SELECT 语句就使用索引：
1. SELECT * FROM tbl_name WHERE key_col LIKE 'Patrick%';
2. SELECT * FROM tbl_name WHERE key_col LIKE 'Pat%_ck%';
在第一个句子中，只会考虑 'Patrick' <= key_col < 'Patricl' 的记录。第二句中，则只会考虑 'Pat' <= key_col < 'Pau' 的记录。
以下 SELECT 语句不使用索引：
1. SELECT * FROM tbl_name WHERE key_col LIKE '%Patrick%';
2. SELECT * FROM tbl_name WHERE key_col LIKE other_col;
第一句里面，LIKE 的值起始于一个通配符。在第二句里，LIKE 的值不是一个常量。如果你这样使用： ... LIKE '%string%'，其中的 string 不大于三个字符，MySql 将使用 Turbo Boyer-Moore 算法来对该字符串表达式进行初始化，并使用这种表达式来让查询更加迅速。如果 col_name 列创建了索引，那么一个使用了 col_name IS NULL 的查询是可以使用该索引的。任何没有涵盖 WHERE 从句中所有 AND 级别的条件的索引将不会被使用。换句话讲，要想使用索引，该索引的前导列必须在每一个 AND 组合中使用到。
以下 WHERE 从句使用索引：
1. ... WHERE index_part1=1 AND index_part2=2 AND other_column=3
4. /* index = 1 OR index = 2 */
5. ... WHERE index=1 OR A=10 AND index=2
8. /* optimized like "index_part1='hello'" */
9. ... WHERE index_part1='hello' AND index_part3=5
12. /* Can use index on index1 but not on index2 or index3 */
13. ... WHERE index1=1 AND index2=2 OR index1=3 AND index3=3;
这些 WHERE 从句不使用索引：
1. /* index_part1 is not used */
2. WHERE index_part2=1 AND index_part3=2
5. /* Index is not used in both parts of the WHERE clause */
6. WHERE index=1 OR A=10
9. /* No index spans all rows */
10. WHERE index_part1=1 OR index_part2=10
有时，即使有索引可以使用，MySQL 也不使用任何索引。发生这种情况的场景之一就是优化器估算出使用该索引将要求 MySql 去访问这张表的绝大部分记录。这种情况下，一个表扫描可能更快，因为它要求更少量的查询。但是，如果这样的一个查询使用了 LIMIT 来检索只是少量的记录时，MySql 还是会使用索引，因为它能够更快地找到这点记录并将其返回。
Hash 索引的特点
Hash 索引有着与刚才所讨论特点的相比截然不同的特点：
- Hash 索引只能够用于使用 = 或者 <=> 运算符的相等比较(但是速度更快)。Hash 索引不能够用于诸如 < 等用于查找一个范围值的比较运算符。依赖于这种单值查找的系统被称为 "键-值存储"；对于这种系统，尽可能地使用 hash 索引。
- 优化器不能够使用 hash 索引来加速 ORDER BY 操作。这种类型的索引不能够用于按照顺序查找下一个条目。
- MySql 无法使用 hash 索引估计两个值之间有多少行(这种情况由范围优化器来决定使用哪个索引)。如果你将一张 MyISAM 或 InnoDB 表转换成一个 hash 索引的内存表时，一些查询可能会受此影响。
- 查找某行记录必须进行全键匹配。而 B-tree 索引，任何该键的左前缀都可用以查找记录。
二、我们应该知其然知其所以然，以下是两种索引的实现原理
首先是 B-Tree
源自：https://www.cnblogs.com/harderman-mapleleaves/p/4528212.html
数据库索引，是数据库管理系统中一个排序的数据结构，以协助快速查询、更新数据库表中数据。索引的实现通常使用B_TREE。B_TREE索引加速了数据访问，因为存储引擎不会再去扫描整张表得到需要的数据；相反，它从根节点开始，根节点保存了子节点的指针，存储引擎会根据指针快速寻找数据。
上图显示了一种索引方式。左边是数据库中的数据表，有col1和col2两个字段，一共有15条记录；右边是以col2列为索引列的B_TREE索引，每个节点包含索引的键值和对应数据表地址的指针，这样就可以都过B_TREE在O(logn)的时间复杂度内获取相应的数据，这样明显地加快了检索的速度。
==============================================================================================================================
B_TREE（来源于数据结构，做个收藏）
1、B_TREE的定义
B_TREE是一种平衡多叉排序树，是一种动态查找效率很高的树形结构。B_TREE中所有结点的孩子结点的最大值称为B_TREE的阶，B_TREE的阶通常用m表示，简称为m叉树。一般来说，应该是m>=3。一颗m阶的B_TREE或是一颗空树，或者是满足下列条件的m叉树：
树中每个结点最多有m个孩子结点；
除根结点外，其它结点至少有(int)m/2+1个孩子结点；
若根结点不是叶子节点，则根结点至少有2个孩子结点；
-
结点的结构：结点的结构
其中，n为结点中关键字个数，(int)m/2<=n<m；di(1<=i<=n)为该结点的n个关键字值的第i个，且di<d(i+1)；ci(0<=i<=n)为该结点孩子结点的指针，且ci所指向的节点的关键字均大于或等于di且小于d(i+1)；
所有的叶结点都在同一层上。
一棵4阶B_TREE的示例。4叉树结点的孩子结点的个数范围[2,4]。其中，有2个结点有4个孩子结点，有1个结点有3个孩子结点，有5个结点有2个孩子结点。
2、B_TREE的查找
在B_TREE上查找x，现将x的关键字与根结点的n个关键字di逐个比较，然后做如下处理：
- 若x.key==di，则查找成功返回；
- 若x.key<d1，则沿着指针c0所指的子树继续查找；
- 若di<x.key<d(i+1)，则沿着指针ci所指的子树继续查找；
- 若x.key>dn，则沿着指针cn所指的子树继续查找。
3、B_TREE的插入
将元素x插入到B_TREE的过程为：
- 查找到x应该插入的结点（插入结点一定是叶结点）；
- 判断该结点是否还有空位置，即判断该结点是否满足结点关键字的个数n小于m-1这个条件。若n<m-1，则说明该结点还有空位置，直接把数据插入（注意插入时要满足B_TREE结点结构定义）；若n=m-1，则需要分裂该结点，即以中间关键字为界（包括要插入的关键字）把结点分为两个结点，并把中间元素向上插入到双亲结点，若双亲结点未满，则把它插入到双亲结点合适的位置，否则，继续往上分裂（直到根结点分裂可能会有树的高度增1的可能）。
4、B_TREE的删除
定义要删除结点x的关键字的个数为n，l=(int)m/2；
- 查找x是否存在，若不存在，则返回；若存在，则继续；
- 对于叶结点上的删除，分为3种情况：1、n>l则直接删除该数据元素；2、n=l且该结点左（右）兄弟结点关键字个数大于l，把删除数据元素结点的左（右）兄弟结点中最大（小）的元素上移到双亲结点上，同时把双亲结点中大于（小于）上移关键字的关键字下移到要删除数据元素的结点上；3、n=l且该结点左（右）兄弟结点关键字个数等于l，把要删除数据元素的结点的左（右）兄弟结点以及双亲结点上分割二者的数据元素合并成一个结点；
- 对于非叶结点的删除，可以转换为叶结点上的删除：假设要删除的元素为di，首先寻找要删除数据元素的结点的ci所指向子树中的最小关键字，设为d(min)，然后把k(min)复制到ki，最后删除关键字为k(min)的元素（此时的k(min)必为某个叶结点上的元素）。
然后是 hash 索引
源自：https://www.cnblogs.com/yimixiong/p/7401527.html
哈希索引是基于哈希表实现的。只有精确匹配索引所有列的的查询才有效。他的实现是存储殷勤会对每一行数据的索引列计算哈希码，并将哈希码和指向该记录的指针维护起来，对于hash相同的，采用链表的方式解决冲突。类似于hashmap。因为索引的结构是十分紧凑的，所以hash索引的查询很快。如此其实我们就很容易的理解hash索引的优缺点了：
1，hash索引只包含了哈希值和行指针，索引不能避免读取行，不能使用覆盖索引。
2，hash索引并不是按照索引顺序存储的，无法用于排序。
3，hash索引不支持部分或者区域查找，部分列的hash结果是不同的。
在Mysql中InnoDB引擎有一个特殊的功能叫做自适应哈希索引，他会在内存中基于B-Tree索引的基础上面创建一个哈希索引，这让B-Tree索引页具备了一些哈希索引的优点。
在《高性能的Mysql》这本树中，作者举了一个自定义哈希索引的列子。假设我们在一个表中大量存储了URL，而且需要根据URL来进行查找。因为URL比较长，这个时候如果我们使用B-Tree索引来，索引会非常的大。解决的办法是在列表中增加一个列，用来存放URL的哈希值，可以通过CRC32对URL进行计算，并存放在列表中，在查找的时候通过CRC32对url进行计算匹配列表中的hash值。
但是这个地方需要注意hash冲突的问题，所以在查询的时候需要添加url的匹配。
例如：where url_crc=CRC32(“http://www.cnblogs.com/yimixiong/p/7400914.html”) and url=” http://www.cnblogs.com/yimixiong/p/7400914.html”
