二、常见的查询算法及数据结构为什么这里要讲查询算法和数据结构呢？因为之所以要建立索引，其实就是为了构建一种数据结构，可以在上面应用一种高效的查询算法，最终提高数据的查询速度。
2.1 索引的本质MySQL官方对索引的定义为：索引（Index）是帮助MySQL高效获取数据的数据结构。提取句子主干，就可以得到索引的本质：索引是数据结构。
2.2 常见的查询算法我们知道，数据库查询是数据库的最主要功能之一。我们都希望查询数据的速度能尽可能的快，因此数据库系统的设计者会从查询算法的角度进行优化。那么有哪些查询算法可以使查询速度变得更快呢？
2.2.1 顺序查找（linear search ）最基本的查询算法当然是顺序查找（linear search），也就是对比每个元素的方法，不过这种算法在数据量很大时效率是极低的。
数据结构：有序或无序队列
复杂度：O(n)
实例代码：
//顺序查找int SequenceSearch(int a[], int value, int n){ int i; for(i=0; i<n; i ) if(a[i]==value) return i; return -1;}
2.2.2 二分查找（binary search）比顺序查找更快的查询方法应该就是二分查找了，二分查找的原理是查找过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
数据结构：有序数组
复杂度：O(logn)
实例代码：
//二分查找，递归版本int BinarySearch2(int a[], int value, int low, int high){ int mid = low (high-low)/2; if(a[mid]==value) return mid; if(a[mid]>value) return BinarySearch2(a, value, low, mid-1); if(a[mid]<value) return BinarySearch2(a, value, mid 1, high);}
2.2.3 二叉排序树查找二叉排序树的特点是：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
搜索的原理：
若b是空树，则搜索失败，否则：
若x等于b的根节点的数据域之值，则查找成功；否则：
若x小于b的根节点的数据域之值，则搜索左子树；否则：
查找右子树。
数据结构：二叉排序树
时间复杂度：O(log2N)
2.2.4 哈希散列法(哈希表)其原理是首先根据key值和哈希函数创建一个哈希表（散列表），燃耗根据键值，通过散列函数，定位数据元素位置。
数据结构：哈希表时间复杂度：几乎是O(1)，取决于产生冲突的多少。
2.2.5 分块查找分块查找又称索引顺序查找，它是顺序查找的一种改进方法。其算法思想是将n个数据元素”按块有序”划分为m块（m ≤ n）。每一块中的结点不必有序，但块与块之间必须”按块有序”；即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，依次类推。算法流程：
先选取各块中的最大关键字构成一个索引表；
查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；然后，在已确定的块中用顺序法进行查找。
这种搜索算法每一次比较都使搜索范围缩小一半。它们的查询速度就有了很大的提升，复杂度为。如果稍微分析一下会发现，每种查找算法都只能应用于特定的数据结构之上，例如二分查找要求被检索数据有序，而二叉树查找只能应用于二叉查找树上，但是数据本身的组织结构不可能完全满足各种数据结构（例如，理论上不可能同时将两列都按顺序进行组织），所以，在数据之外，数据库系统还维护着满足特定查找算法的数据结构，这些数据结构以某种方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。
2.3 平衡多路搜索树B树（B-tree）
上面讲到了二叉树，它的搜索时间复杂度为O(log2N)，所以它的搜索效率和树的深度有关，如果要提高查询速度，那么就要降低树的深度。要降低树的深度，很自然的方法就是采用多叉树，再结合平衡二叉树的思想，我们可以构建一个平衡多叉树结构，然后就可以在上面构建平衡多路查找算法，提高大数据量下的搜索效率。
2.3.1 B TreeB树（Balance Tree）又叫做B- 树（其实B-是由B-tree翻译过来，所以B-树和B树是一个概念） ，它就是一种平衡多路查找树。下图就是一个典型的B树：
从上图中我们可以大致看到B树的一些特点，为了更好的描述B树，我们定义记录为一个二元组[key, data]，key为记录的键值，data表示其它数据（上图中只有key，没有画出data数据 ）。下面是对B树的一个详细定义：1. 有一个根节点，根节点只有一个记录和两个孩子或者根节点为空；2. 每个节点记录中的key和指针相互间隔，指针指向孩子节点；3. d是表示树的宽度，除叶子节点之外，其它每个节点有[d/2,d-1]条记录，并且些记录中的key都是从左到右按大小排列的，有[d/2 1,d]个孩子；4. 在一个节点中，第n个子树中的所有key，小于这个节点中第n个key，大于第n-1个key，比如上图中B节点的第2个子节点E中的所有key都小于B中的第2个key 9，大于第1个key 3;5. 所有的叶子节点必须在同一层次，也就是它们具有相同的深度；
由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。B-Tree上查找算法的伪代码如下：
BTree_Search(node, key) { if(node == null) return null; foreach(node.key){ if(node.key[i] == key) return node.data[i]; if(node.key[i] > key) return BTree_Search(point[i]->node); } return BTree_Search(point[i 1]->node); }data=BTree_Search(root,my_key)
关于B-Tree有一系列有趣的性质，例如一个度为d的B-Tree，设其索引N个key，则其树高h的上限为logd((N 1)/2)，检索一个key，其查找节点个数的渐进复杂度为O(logdN)。从这点可以看出，B-Tree是一个非常有效率的索引数据结构。另外，由于插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质，本文不打算完整讨论B-Tree这些内容，因为已经有许多资料详细说明了B-Tree的数学性质及插入删除算法，有兴趣的朋友可以查阅其它文献进行详细研究。
2.3.2 B Tree其实B-Tree有许多变种，其中最常见的是B Tree，比如MySQL就普遍使用B Tree实现其索引结构。B-Tree相比，B Tree有以下不同点：
每个节点的指针上限为2d而不是2d 1；
内节点不存储data，只存储key；
叶子节点不存储指针；
下面是一个简单的B Tree示意。
由于并不是所有节点都具有相同的域，因此B Tree中叶节点和内节点一般大小不同。这点与B-Tree不同，虽然B-Tree中不同节点存放的key和指针可能数量不一致，但是每个节点的域和上限是一致的，所以在实现中B-Tree往往对每个节点申请同等大小的空间。一般来说，B Tree比B-Tree更适合实现外存储索引结构，具体原因与外存储器原理及计算机存取原理有关，将在下面讨论。
2.3.3 带有顺序访问指针的B Tree一般在数据库系统或文件系统中使用的B Tree结构都在经典B Tree的基础上进行了优化，增加了顺序访问指针。
如图所示，在B Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B Tree。做这个优化的目的是为了提高区间访问的性能，例如图4中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。这一节对B-Tree和B Tree进行了一个简单的介绍，下一节结合存储器存取原理介绍为什么目前B Tree是数据库系统实现索引的首选数据结构。
三、索引数据结构设相关的计算机原理上文说过，二叉树、红黑树等数据结构也可以用来实现索引，但是文件系统及数据库系统普遍采用B-/ Tree作为索引结构，这一节将结合计算机组成原理相关知识讨论B-/ Tree作为索引的理论基础。
3.1 两种类型的存储在计算机系统中一般包含两种类型的存储，计算机主存（RAM）和外部存储器（如硬盘、CD、SSD等）。在设计索引算法和存储结构时，我们必须要考虑到这两种类型的存储特点。主存的读取速度快，相对于主存，外部磁盘的数据读取速率要比主从慢好几个数量级，具体它们之间的差别后面会详细介绍。上面讲的所有查询算法都是假设数据存储在计算机主存中的，计算机主存一般比较小，实际数据库中数据都是存储到外部存储器的。
一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。下面详细介绍内存和磁盘存取原理，然后再结合这些原理分析B-/ Tree作为索引的效率。
3.2 主存存取原理目前计算机使用的主存基本都是随机读写存储器（RAM），现代RAM的结构和存取原理比较复杂，这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理。
寻道时间是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下。
旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms。
传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。
那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5 4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。
3.4 局部性原理与磁盘预读由于存储介质的特性，磁盘本身存取就比主存慢很多，再加上机械运动耗费，磁盘的存取速度往往是主存的几百分分之一，因此为了提高效率，要尽量减少磁盘I/O。为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。由于磁盘顺序读取的效率很高（不需要寻道时间，只需很少的旋转时间），因此对于具有局部性的程序来说，预读可以提高I/O效率。预读的长度一般为页（page）的整倍数。页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块，每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号，磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。
四、数据库索引所采用的数据结构B-/ Tree及其性能分析到这里终于可以分析为何数据库索引采用B-/ Tree存储结构了。上文说过数据库索引是存储到磁盘的而我们又一般以使用磁盘I/O次数来评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h-1个节点（根节点常驻内存）。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。B-Tree中一次检索最多需要h-1次I/O（根节点常驻内存），渐进复杂度为O(h)=O(logdN)。一般实际应用中，出度d是非常大的数字，通常超过100，因此h非常小（通常不超过3）。综上所述，如果我们采用B-Tree存储结构，搜索时I/O次数一般不会超过3次，所以用B-Tree作为索引结构效率是非常高的。
4.1 B 树性能分析从上面介绍我们知道，B树的搜索复杂度为O(h)=O(logdN)，所以树的出度d越大，深度h就越小，I/O的次数就越少。B Tree恰恰可以增加出度d的宽度，因为每个节点大小为一个页大小，所以出度的上限取决于节点内key和data的大小：
dmax=floor(pagesize/(keysize datasize pointsize))//floor表示向下取整
由于B Tree内节点去掉了data域，因此可以拥有更大的出度，从而拥有更好的性能。
4.2 B 树查找过程
五、MySQL索引实现在MySQL中，索引属于存储引擎级别的概念，不同存储引擎对索引的实现方式是不同的，本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。
MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B Tree，非单调的主键会造成在插入新记录时数据文件为了维持B Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。六、索引使用策略及优化
MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础，实际上一旦理解了索引背后的机制，那么选择高性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。
6.1 联合索引及最左前缀原理
联合索引（复合索引）首先介绍一下联合索引。联合索引其实很简单，相对于一般索引只有一个字段，联合索引可以为多个字段创建一个索引。它的原理也很简单，比如，我们在（a,b,c）字段上创建一个联合索引，则索引记录会首先按照A字段排序，然后再按照B字段排序然后再是C字段，因此，联合索引的特点就是：
第一个字段一定是有序的
当第一个字段值相等的时候，第二个字段又是有序的，比如下表中当A=2时所有B的值是有序排列的，依次类推，当同一个B值得所有C字段是有序排列的
| A | B | C | | 1 | 2 | 3 | | 1 | 4 | 2 | | 1 | 1 | 4 | | 2 | 3 | 5 | | 2 | 4 | 4 | | 2 | 4 | 6 | | 2 | 5 | 5 |其实联合索引的查找就跟查字典是一样的，先根据第一个字母查，然后再根据第二个字母查，或者只根据第一个字母查，但是不能跳过第一个字母从第二个字母开始查。这就是所谓的最左前缀原理。
最左前缀原理我们再来详细介绍一下联合索引的查询。还是上面例子，我们在（a,b,c）字段上建了一个联合索引，所以这个索引是先按a 再按b 再按c进行排列的，所以：以下的查询方式都可以用到索引
select * from table where a=1；select * from table where a=1 and b=2；select * from table where a=1 and b=2 and c=3；
上面三个查询按照 （a ）, （a，b ）,（a，b，c ）的顺序都可以利用到索引，这就是最左前缀匹配。如果查询语句是：
select*fromtablewherea=1andc=3；那么只会用到索引a。
如果查询语句是：
select * from table where b=2 and c=3；因为没有用到最左前缀a，所以这个查询是用户到索引的。
如果用到了最左前缀，但是顺序颠倒会用到索引码？比如：
select * from table where b=2 and a=1；select * from table where b=2 and a=1 and c=3；
如果用到了最左前缀而只是颠倒了顺序，也是可以用到索引的，因为mysql查询优化器会判断纠正这条sql语句该以什么样的顺序执行效率最高，最后才生成真正的执行计划。但我们还是最好按照索引顺序来查询，这样查询优化器就不用重新编译了。
前缀索引除了联合索引之外，对mysql来说其实还有一种前缀索引。前缀索引就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。一般来说以下情况可以使用前缀索引：
字符串列(varchar,char,text等)，需要进行全字段匹配或者前匹配。也就是=‘xxx’ 或者 like ‘xxx%’
前一半字符的索引选择性就已经接近于全字段的索引选择性。如果整个字段的长度为20，索引选择性为0.9，而我们对前10个字符建立前缀索引其选择性也只有0.5，那么我们需要继续加大前缀字符的长度，但是这个时候前缀索引的优势已经不明显，没有太大的建前缀索引的必要了。
一些文章中也提到：MySQL 前缀索引能有效减小索引文件的大小，提高索引的速度。但是前缀索引也有它的坏处：MySQL 不能在 ORDER BY 或 GROUP BY 中使用前缀索引，也不能把它们用作覆盖索引(Covering Index)。
6.2 索引优化策略
最左前缀匹配原则，上面讲到了
主键外检一定要建索引
对 where,on,group by,order by 中出现的列使用索引
尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0
对较小的数据列使用索引,这样会使索引文件更小,同时内存中也可以装载更多的索引键
索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b 树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
为较长的字符串使用前缀索引
尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可
不要过多创建索引, 权衡索引个数与DML之间关系，DML也就是插入、删除数据操作。这里需要权衡一个问题，建立索引的目的是为了提高查询效率的，但建立的索引过多，会影响插入、删除数据的速度，因为我们修改的表数据，索引也需要进行调整重建
对于like查询，”%”不要放在前面。
SELECT * FROMhoudunwangWHEREunameLIKE’后盾%’ — 走索引SELECT * FROMhoudunwangWHEREunameLIKE “%后盾%” — 不走索引
查询where条件数据类型不匹配也无法使用索引
字符串与数字比较不使用索引;CREATE TABLEa(achar(10));EXPLAIN SELECT * FROMaWHEREa=”1″ – 走索引EXPLAIN SELECT * FROM a WHERE a=1 – 不走索引正则表达式不使用索引,这应该很好理解，所以为什么在SQL中很难看到regexp关键字的原因
参考文章：
https://blog.csdn.net/suifeng3051/article/details/52669644
-END-
【推荐阅读】
这几道Redis面试题都不懂，怎么拿offer
如何写出让同事无法维护的代码
使用docker部署spring cloud项目详细步骤
