目录

1.1 常见查找方法举例
1.2 索引数据结构设相关的计算机原理
1.3 MyISAM实现索引
1.4 InnoDB索引实现
1.5 索引使用策略

1.1 常见查找方法举例

1、顺序查找（linear search ）

1. 最基本的查询算法当然是顺序查找（linear search），也就是对比每个元素的方法，不过这种算法在数据量很大时效率是极低的。

2. 数据结构：有序或无序队列

3. 复杂度：O(n)

2、二分查找

1. 从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；

2. 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且根开始一样从中间元素开始比较。

3. 如果在某一步骤数组为空，则代表找不到。

4. 数据结构：有序数组

5. 复杂度：O(logn)

3、二叉排序树查找

1）二叉排序树的特点是：

　　　　　　　　1. 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

　　　　　　　　2. 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

　　　　　　　　3. 它的左、右子树也分别为二叉排序树。

　　　　2）搜索的原理：

　　　　　　　　若b是空树，则搜索失败，否则：
　　　　　　　　若x等于b的根节点的数据域之值，则查找成功；否则：
　　　　　　　　若x小于b的根节点的数据域之值，则搜索左子树；否则：
　　　　　　　　查找右子树。

　　　　　　　　数据结构：二叉排序树

　　　　　　　　时间复杂度： O(log2N)

4、哈希散列法(哈希表)

1. 其原理是首先根据key值和哈希函数创建一个哈希表（散列表），燃耗根据键值，通过散列函数，定位数据元素位置。

2. 数据结构：哈希表

3. 时间复杂度：几乎是O(1)，取决于产生冲突的多少。

1.2 索引数据结构设相关的计算机原理

1、计算机主存和外部存 介绍

1. 在计算机系统中一般包含两种类型的存储，计算机主存（RAM）和外部存储器（如硬盘、CD、SSD等）。

        2. 在设计索引算法和存储结构时，我们必须要考虑到这两种类型的存储特点。

        3. 主存的读取速度快，相对于主存，外部磁盘的数据读取速率要比主从慢好几个数量级，具体它们之间的差别后面会详细介绍。

        4. 上面讲的所有查询算法都是假设数据存储在计算机主存中的，计算机主存一般比较小，实际数据库中数据都是存储到外部存储器的。

2、如何评价索引性能

1. 一般来说，索引本身也很大，不可能全部存储在内存中，因此索引往往以索引文件的形式存储的磁盘上。

        2. 这样的话，索引查找过程中就要产生磁盘I/O消耗，相对于内存存取，I/O存取的消耗要高几个数量级。

        3. 所以评价一个数据结构作为索引的优劣最重要的指标就是在查找过程中磁盘I/O操作次数的渐进复杂度。

        4. 换句话说，索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数。

3、主存存取原理

注：这里本文抛却具体差别，抽象出一个十分简单的存取模型来说明RAM的工作原理

        1. 从抽象角度看，主存是一系列的存储单元组成的矩阵，每个存储单元存储固定大小的数据。

        2. 每个存储单元有唯一的地址，现代主存的编址规则比较复杂，这里将其简化成一个二维地址。

        3. 通过一个行地址和一个列地址可以唯一定位到一个存储单元。

　　　　如图展示了一个4 x 4的主存模型：
        ![](https://img2018.cnblogs.com/blog/1844658/202001/1844658-20200108225217163-2084602286.png)


　　　　　　

        主存的存取过程如下：
            1）当系统需要读取主存时，则将地址信号放到地址总线上传给主存，主存读到地址信号后，
　　　　　　　　　　解析信号并定位到指定存储单元，然后将此存储单元数据放到数据总线上，供其它部件读取。

            2）写主存的过程类似，系统将要写入单元地址和数据分别放在地址总线和数据总线上，主存读取两个总线的内容，做相应的写操作。

            3）这里可以看出，主存存取的时间仅与存取次数呈线性关系，因为不存在机械操作，两次存取的数据的“距离”不会对时间有任何影响

            4）例如，先取A0再取A1和先取A0再取D3的时间消耗是一样的。

4、磁盘存取原理

1. 索引一般以文件形式存储在磁盘上，索引检索需要磁盘I/O操作。

　　　　　　2. 与主存不同，磁盘I/O存在机械运动耗费，因此磁盘I/O的时间消耗是巨大的。

　　　　　　3. 磁盘读取数据靠的是机械运动，当需要从磁盘读取数据时，系统会将数据逻辑地址传给磁盘。

　　　　　　4. 磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址，即确定要读的数据在哪个磁道，哪个扇区。

　　　　　　5. 为了读取这个扇区的数据，需要将磁头放到这个扇区上方，为了实现这一点，磁头需要移动对准相应磁道，这个过程叫做寻道。

　　　　　　6. 所耗费时间叫做寻道时间，然后磁盘旋转将目标扇区旋转到磁头下，这个过程耗费的时间叫做旋转时间，最后便是对读取数据的传输。

　　　　　　7. 所以每次读取数据花费的时间可以分为 寻道时间、旋转延迟、传输时间 三个部分。

　　　　　　　　1）寻道时间是磁臂移动到指定磁道所需要的时间，主流磁盘一般在5ms以下。
　　　　　　　　2）旋转延迟就是我们经常听说的磁盘转速，比如一个磁盘7200转，表示每分钟能转7200次，也就是说1秒钟能转120次，旋转延迟就是1/120/2 = 4.17ms。
　　　　　　　　3）传输时间指的是从磁盘读出或将数据写入磁盘的时间，一般在零点几毫秒，相对于前两个时间可以忽略不计。

　　　　　　8. I/O操作巨大问题

　　　　　　　　1）那么访问一次磁盘的时间，即一次磁盘IO的时间约等于5+4.17 = 9ms左右
　　　　　　　　2）听起来还挺不错的，但要知道一台500 -MIPS的机器每秒可以执行5亿条指令
　　　　　　　　3）因为指令依靠的是电的性质，换句话说执行一次IO的时间可以执行40万条指令
　　　　　　　　4）数据库动辄十万百万乃至千万级数据，每次9毫秒的时间，显然是个灾难。

5、磁盘预读

因此为了提高效率，要尽量减少磁盘I/O，为了达到这个目的，磁盘往往不是严格按需读取，而是每次都会预读。

　　　　　　即使只需要一个字节，磁盘也会从这个位置开始，顺序向后读取一定长度的数据放入内存。

　　　　　　这样做的理论依据是计算机科学中著名的局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用。

　　　　　　预读的长度一般为页（page）的整倍数。

　　　　　　页是计算机管理存储器的逻辑块，硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块

　　　　　　每个存储块称为一页（在许多操作系统中，页得大小通常为4k），主存和磁盘以页为单位交换数据。

　　　　　　当程序要读取的数据不在主存中时，会触发一个缺页异常，此时系统会向磁盘发出读盘信号

　　　　　　磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中，然后异常返回，程序继续运行。

6、B-Tree/B+Tree存储结构

1. 到这里终于可以分析为何数据库索引采用B-/+Tree存储结构了。

　　　　　　2. 上文说过数据库索引是存储到磁盘的而我们又一般以使用磁盘I/O次数来评价索引结构的优劣。

　　　　　　3. 先从B-Tree分析，根据B-Tree的定义，可知检索一次最多需要访问h-1个节点（根节点常驻内存）。

　　　　　　4. 数据库系统的设计者巧妙利用了磁盘预读原理，将一个节点的大小设为等于一个页，这样每个节点只需要一次I/O就可以完全载入。

　　　　　　5. 为了达到这个目的，在实际实现B-Tree还需要使用如下技巧：

　　　　　　　　　　1） 每次新建节点时，直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，
　　　　　　　　　　2）加之计算机存储分配都是按页对齐的，就实现了一个node只需一次I/O。

1.3 MyISAM实现索引

1、MyISAM实现索引 介绍

1. MyISAM引擎使用B+Tree作为索引结构，叶节点的data域存放的是数据记录的地址。

        2. MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引。

        3. 如果指定的Key存在，则取出其data域的值，然后以data域的值为地址，读取相应数据记录。

        4. MyISAM的索引方式也叫做“非聚集”的，之所以这么称呼是为了与InnoDB的聚集索引区分。

*2、MyISAM索引的原理图

• 1. 这里设表一共有三列，假设我们以Col1为主键，则上图是一个MyISAM表的主索引（Primary key）示意。
• 1. 可以看出MyISAM的索引文件仅仅保存数据记录的地址。
     

1.4 InnoDB索引实现

注：虽然InnoDB也使用B+Tree作为索引结构，但具体实现方式却与MyISAM截然不同。

1、区别1：InnoDB的数据文件本身就是索引文件

　　　　1. 从上文知道，MyISAM索引文件和数据文件是分离的，索引文件仅保存数据记录的地址。

　　　　2. 而在InnoDB中，表数据文件本身就是按B+Tree组织的一个索引结构，这棵树的叶节点data域保存了完整的数据记录。

　　　　3. 这个索引的key是数据表的主键，因此InnoDB表数据文件本身就是主索引。

说明：

　　　　　　可以看到叶节点包含了完整的数据记录，这种索引叫做聚集索引。

　　　　　　因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有）

　　　　　　如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键

　　　　　　如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。

2、区别2：InnoDB的辅助索引data域存储相应记录主键的值而不是地址

　　　　1. 换句话说，InnoDB的所有辅助索引都引用主键作为data域。

　　　　2. 这里以英文字符的ASCII码作为比较准则。

　　　　3. 聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引

　　　　4. 首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。

3、为什么不建议使用过长的字段作为主键

　　　　1. 例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键

　　　　2. 因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。

　　　　3. 再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，

　　　　4. 非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。

1.5 索引使用策略

1、联合索引（复合索引）

　　　　1. 联合索引其实很简单，相对于一般索引只有一个字段，联合索引可以为多个字段创建一个索引

　　　　2. 它的原理也很简单，比如，我们在（a,b,c）字段上创建一个联合索引，则索引记录会首先按照A字段排序，然后再按照B字段排序然后再是C字段

　　　　3. 其实联合索引的查找就跟查字典是一样的，先根据第一个字母查，然后再根据第二个字母查

　　　　4. 或者只根据第一个字母查，但是不能跳过第一个字母从第二个字母开始查。这就是所谓的最左前缀原理。

　　　　5. 联合索引的特点就是：

　　　　　　1）第一个字段一定是有序的
　　　　　　　　2）当第一个字段值相等的时候，第二个字段又是有序的，比如下表中当A=2时所有B的值是有序排列的，依次类推，当同一个B值得所有C字段是有序排列的

'''最左前缀原理'''

#### 1、以下的查询方式都可以用到索引
'''
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 ）的顺序都可以利用到索引，这就是最左前缀匹配。
'''

#### 2、如果查询语句是：
'''
select * from table where a=1 and c=3； 那么只会用到索引a。
'''

#### 3、这样不会用的索引
'''
select * from table where b=2 and c=3； 因为没有用到最左前缀a，所以这个查询是用户到索引的。
'''

2、前缀索引

　　　　　　1. 前缀索引就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引

　　　　　　2. 同时因为索引key变短而减少了索引文件的大小和维护开销。

　　　　　　3. 一般来说以下情况可以使用前缀索引：

　　　　　　　　1）字符串列(varchar,char,text等)，需要进行全字段匹配或者前匹配。也就是=‘xxx’ 或者 like ‘xxx%’
　　　　　　　　2）字符串本身可能比较长，而且前几个字符就开始不相同。（比如：收件地址、外国人的姓名）

　　　　　　4. MySQL 前缀索引能有效减小索引文件的大小，提高索引的速度。

　　　　　　5. 但是前缀索引也有它的坏处：MySQL 不能在 ORDER BY 或 GROUP BY 中使用前缀索引，也不能把它们用作覆盖索引(Covering Index)。

3、索引优化策略

说明：MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。

# 1、最左前缀匹配原则，上面讲到了
# 2、主键外键一定要建索引
# 3、对 where,on,group by,order by 中出现的列使用索引
# 4、尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，
# 5、为较长的字符串使用前缀索引

'''
# 6、不要过多创建索引, 权衡索引个数与DML之间关系，DML也就是插入、删除数据操作。
    这里需要权衡一个问题，建立索引的目的是为了提高查询效率的，但建立的索引过多，
    会影响插入、删除数据的速度，因为我们修改的表数据，索引也需要进行调整重建
'''

'''
# 7、对于like查询，”%”不要放在前面。
    SELECT * FROMhoudunwangWHEREunameLIKE'后盾%' -- 走索引 
    SELECT * FROMhoudunwangWHEREunameLIKE "%后盾%" -- 不走索引
'''

'''
# 8、查询where条件数据类型不匹配也无法使用索引 
    字符串与数字比较不使用索引; 
    CREATE TABLEa(achar(10)); 
    EXPLAIN SELECT * FROMaWHEREa="1" – 走索引 
    EXPLAIN SELECT * FROM a WHERE a=1 – 不走索引 
    正则表达式不使用索引,这应该很好理解,所以为什么在SQL中很难看到regexp关键字的原因
'''

建索引原则

建索引原则：

1.最左前缀匹配原则，非常重要的原则，mysql会一直向右匹配直到遇到范围查询(>、<、between、like)就停止匹配，
比如a = 1 and b = 2 and c > 3 and d = 4 如果建立(a,b,c,d)顺序的索引，d是用不到索引的，
如果建立(a,b,d,c)的索引则都可以用到，a,b,d的顺序可以任意调整。

2.=和in可以乱序，比如a = 1 and b = 2 and c = 3 建立(a,b,c)索引可以任意顺序，
mysql的查询优化器会帮你优化成索引可以识别的形式

3.尽量选择区分度高的列作为索引,区分度的公式是count(distinct col)/count(*)，表示字段不重复的比例，
比例越大我们扫描的记录数越少，唯一键的区分度是1，而一些状态、性别字段可能在大数据面前区分度就是0，
那可能有人会问，这个比例有什么经验值吗？使用场景不同，这个值也很难确定，
一般需要join的字段我们都要求是0.1以上，即平均1条扫描10条记录

4.索引列不能参与计算，保持列“干净”，比如from_unixtime(create_time) = ’2014-05-29’就不能使用到索引，
原因很简单，b+树中存的都是数据表中的字段值，但进行检索时，需要把所有元素都应用函数才能比较，
显然成本太大。所以语句应该写成create_time = unix_timestamp(’2014-05-29’);

5.尽量的扩展索引，不要新建索引。比如表中已经有a的索引，现在要加(a,b)的索引，那么只需要修改原来的索引即可