极客–深入浅出索引

索引是怎样工作的？

索引的出现是提高数据查询效率，就像教科书中的目录一样。

索引的常见模型

• 哈希表

  
  
  
  

  • 哈希表是一种以键值存储的结构，我们只需要输入待查找的键即为key，就可以找到对应的值Value.哈希的思路很简单，把值放大数组里，用一个哈希函数把key换算成一个确定的位置，然后把value放在数组的这个位置

    
    
  
  

  • 多个key值经过哈希函数换算，会出现同一个值的情况。处理这种情况的方法是拉链法

    
    
  
  

  • 哈希索引做区间查询的速度很慢

    
    
  
  

  • 哈希表这种结构适用于等值查询场景，比如Memcached及其他一些，NoSQL引擎

    
    
  
  
  
  



• 有序数组

  
  
  
  

  • 有序数组在等值查询和范围查询场景性能都非常优秀

    
    
  
  

  • 如果使用有序数组使用身份证号递增的顺序，按照二分法查询，如果从查询效率，有序数组是最好的，但是插入一个记录需要挪动后面所有的记录成本太高

    
    
  
  

  • 有序数组适用于静态存储引擎

    
    
  
  
  
  



• 搜索树

  
  
  
  
  • 二叉搜索树:父节点的左子树所有节点的值小于父节点的值，右子树所有节点的值大于父节点的值，为了维持O(log(N))的时间复杂度，就需要保证这棵树更新时间复杂度为O(log(N))
  
  
  • 二叉树的搜索效率是最高的，但是实际大多数的数据库存储却不使用二叉树，其原因。索引不止存在内存中，还要写在磁盘上。
  
  
  • 如果一棵树100万个节点的平衡二叉树，树高20.一次查询可能需要访问20个数据块。在机械硬盘时代，从磁盘随机读一个数据块需要10ms左右的寻址空间，也就是说，对于100万行表，如果使用二叉树来存储，单独访问一个行可能需要20个10ms，这个查询速度太慢了
  
  
  • 为了减少查询尽量少的读取磁盘，就必须查询过程访问尽量少的数据块，那么，我们就不该用二叉树，而是用N叉树
  
  
  
  

以 InnoDB 的一个整数字段索引为例，这个 N 差不多是 1200。这棵树高是 4 的时候，就可以存 1200 的 3 次方个值，这已经 17 亿了。考虑到树根的数据块总是在内存中的，一个 10 亿行的表上一个整数字段的索引，查找一个值最多只需要访问 3 次磁盘

N叉树由于读写上的性能特点，以及适配磁盘的访问模式，已经被广泛应用在数据库引擎中

Innodb索引模型

• Innodb中表根据主键顺序以索引方式存放的，这种存储方式的表为索引组织表，Innodb使用B+树索引模型，所以数据都是存储在B+树中

  
  



• 每一个索引在Innodb里面对应一棵B+树

  
  



• 主键索引叶子节点存放的是整行数据，二级索引叶子节点存储的是二级索引

  
  

基于主键索引和普通索引的查询区别是什么？

• 根据主键索引查询方式，只需要搜索ID这棵树B+树


• 则需要先搜索K索引树，得到ID值500，再到ID索引树搜索一次，这个过程称为回表

索引维护

B+树为了维护索引有序性，在插入新值的时候需要必要的维护

• 如果插入ID为700直接在R5后面插入即可，如果插入400需要逻辑上面挪动后面的数据，如果R5所在数据页已经满了，根据B+树算法，这时候需要申请一个数据页，然后挪动部分数据过去，这个过程叫做页分裂，这种情况下性能会下降

  
  



• 除了性能外，页分裂操作还会影响数据页利用率，原本放在一个页的数据分为两页，整体空间利用率降低50%

  
  



• 当相邻两个页由于删除了数据，利用率很低之后，会将数据页做合并。合并的过程，可以认为是分裂过程的逆过程。

  
  



• 自增主键每次插入一条新纪录都是追加操作，都不涉及到挪动其他记录，也不会触发叶分裂

  
  



• 只有一个索引，该索引必须是唯一索引的时候可以考虑业务字段作为主键

  
  

Innodb使用了B+树结构，B+树能够很好地配合磁盘读写特性，减少单次查询磁盘访问次数。由于Innodb是索引组织表，一般情况下我会建议你创建一个自增主键，这样非主键索引占用空间最小

• 由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段

最左前缀原则

B+树这种索引结构，可以利用索引的最左前缀，来定位记录，联合索引考虑空间与复用

索引下推

检索出表中“名字第一个字是张，而且年龄是 10 岁的所有男孩”。那么，SQL 语句是这么写的：

mysql> select * from tuser where name like '张%' and age=10 and ismale=1;

Mysql5.6引入索引下推优化，可以索引遍历过程中，对索引包含的字段先做判断，直接过滤掉不满足的记录，减少汇报次数。InnoDB在(name,age)索引下推的过程中判断age的存在，减少一次次数