我们能对数据库进行什么操作？无非就是增删改查。并且查询在这些功能中是占很大比例的，如果数据量不是很大，我们可能无法感受查询快慢带来的不同体验，但是当数据量到达一定量级的时候，我们就能深刻体会不同查询方式的查询效率的差别之大，我们都知道，索引能在很大程度上提高查询效率，但是是为什么呢？  以下是我自己看了很多博客，借鉴了很多其他博主对索引的理解，算是自己的一些学习心得，很多图片和文字并非自己完全原创。 如果有幸被其他被引用资源的博主看到，请见谅。  

       在计算机系统中一般包含两种类型的存储，计算机主存（RAM）和外部存储器（如硬盘、CD、SSD等）。在设计索引算法和存储结构时，我们必须要考虑到这两种类型的存储特点。主存的读取速度快，相对于主存，外部磁盘的数据读取速率要比主从慢好几个数量级，具体它们之间的差别后面会详细介绍。 上面讲的所有查询算法都是假设数据存储在计算机主存中的，计算机主存一般比较小，实际数据库中数据都是存储到外部存储器的。

       一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级，所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。
       我们先看一下主存存储原理和磁盘存储原理的差别。

     当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响，例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

         而磁盘存储不一样。        

        磁盘读取数据靠的是机械运动，当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘，磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道，所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间，最后便是对读取数据的传输。 所以每次读取数据花费的时间可以分为寻道时间、旋转延迟、传输时间三个部分。其中：

       寻道时间是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下。
       旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转         延迟就是1/120/2 = 4.17ms。
       传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。
        那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右，听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令，因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令，数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。

        磁盘为了减少I/O，为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读，即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。程序运行期间所需要的数据通常比较集中。

        索引的实现方式有很多，不同的存储引擎有不同的实现方式，但是主要可以分为五种。B-TREE索引，bitmap索引（位图索引），HASH索引，聚族索引，非聚族索引，不过需要注意，存储引擎在建立索引的时候默认是B-TREE索引。不过对于MYSQL的两种引擎，B-TREE实现的方式也不一样，这个稍后会说到。

       我们重点说一下B-TREE（平衡多路搜索B树）。

       我们知道二叉树的时间复杂度是O（log2N）,树的深度越深，就意味查询越慢，所以我们要尽量降低树的深度，那多路的平衡树就是一个不错的选择。这是B树的一个结构一个

       由于B-Tree的特性，在B-Tree中按key检索数据的算法非常直观：首先从根节点进行二分查找，如果找到则返回对应节点的data，否则对相应区间的指针指向的节点递归进行查找，直到找到节点或找到null指针，前者查找成功，后者查找失败。当然了，删除和增加不是我们讨论的重点，但是我们需要知道，插入删除新的数据记录会破坏B-Tree的性质，因此在插入删除时，需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。

        B树有很多的变种，其中B+树就是很好的一个例子，下面是B+树的一个结构示意图。

     与B树对比，B+树的改进主要体现在三个方面：

     1.每个节点的指针上限为2d而不是2d+1；

     2.内节点不存储data，只存储key；

     3.叶子节点不存储指针；

     不过对于数据库或者文件存储系统，使用的B+Tree结构都在经典B+Tree的基础上进行了优化，增加了顺序访问指针。如下所示。

       这样在一定程度上。在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针，就形成了带有顺序访问指针的B+Tree。做这个优化的目的是为了提高区间访问的性能。例如上图中如果要查询key为从18到49的所有数据记录，当找到18后，只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点，极大提到了区间查询效率。

       数据库索引是存储到磁盘的而我们又一般以使用磁盘I/O次数来评价索引结构的优劣。先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h-1个节点（根节点常驻内存）。数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。我们采用B-Tree存储结构，搜索时I/O次数一般不会超过3次，所以用B-Tree作为索引结构效率是非常高的。

       那B+树是怎么实现查找的呢？下面我们来分析一下。

      如上图所示，如果要查找数据项29，那么首先会把磁盘块1由磁盘加载到内存，此时发生一次IO，在内存中用二分查找确定29在17和35之间，锁定磁盘块1的P2指针，内存时间因为非常短（相比磁盘的IO）可以忽略不计，通过磁盘块1的P2指针的磁盘地址把磁盘块3由磁盘加载到内存，发生第二次IO，29在26和30之间，锁定磁盘块3的P2指针，通过指针加载磁盘块8到内存，发生第三次IO，同时内存中做二分查找找到29，结束查询，总计三次IO。真实的情况是，3层的b+树可以表示上百万的数据，如果上百万的数据查找只需要三次IO，性能提高将是巨大的，如果没有索引，每个数据项都要发生一次IO，那么总共需要百万次的IO，显然成本非常非常高。

        我们在上文中已经说到了，索引属于存储引擎的范畴，所以不同的存储引擎有不同的索引方式，我们以MYSQL里面的两种存储引擎MyISAM和InnoDB为例。

       首先是MyISAM。

             可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中，主索引和辅助索引（Secondary key）在结构上没有任何区别，只是主索引要求key是唯一的，而辅助索引的key可以重复。

        InnoDB：

        叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

        通过这些，根据其他一些博客，有以下的优化策略。

       最左前缀匹配原则，上面讲到了最左前缀匹配原则，上面讲到了
      1.主键外检一定要建索引
      2. 对 where,on,group by,order by 中出现的列使用索引
      3.尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，比例越大我们扫描的 记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0对较小的数据列使用索引,这样会使索引文件更小,同时内存中也可以装载更多的索引键索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);
      4.为较长的字符串使用前缀索引
      5.尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可
      6.不要过多创建索引, 权衡索引个数与DML之间关系，DML也就是插入、删除数据操作。这里需要权衡一个问题，建立索引的目的是为了提高查询效率的，但建立的索引过多，会影响插入、删除数据的速度，因为我们修改的表数据，索引也需要进行调整重建
      7.对于like查询，”%”不要放在前面。 
       SELECT * FROMhoudunwangWHEREunameLIKE'后盾%' -- 走索引 
      SELECT * FROMhoudunwangWHEREunameLIKE "%后盾%" -- 不走索引
     8.查询where条件数据类型不匹配也无法使用索引 
     9.字符串与数字比较不使用索引; 
       CREATE TABLEa(achar(10)); 
            EXPLAIN SELECT * FROMaWHEREa="1" – 走索引 
            EXPLAIN SELECT * FROM a WHERE a=1 – 不走索引 
     10.正则表达式不使用索引,这应该很好理解,所以为什么在SQL中很难看到regexp关键字的原因