Mysql-索引与算法

B+树索引的管理

• 创建索引

  对于索引的添加或删除，MySQL先创建一张临时表，把数据导入临时表，删除原表，然后把临时表重命名为原来的表。因此大表创建和删除索引的时间非常长。

  快速索引创建法：对于非聚集索引的创建，InnoDB会对表加S锁，创建过程中只能读，不能写。

B+树索引的使用

• 顺序读

  顺序的读取磁盘上的块

• 随机读

  访问的块不连续，需要磁头不断移动

• 预读取

  通过一次I/O请求多个页预读到缓冲池中，并且估计预读的多个页马上会被访问。传统I/O请求每次只读取一个页，在传统机械硬盘较低的IOPS下，预读计数可以大大提高读取的性能。

  1. 随机预读

     当一个区中==13==个页在缓冲区中，并在LRU列表的前端，则InnoDB存储引擎会将这个区中剩余的所有页都预读到缓冲区。

     InnoDB Plugin 1.0.4开始，随机预读被取消。

  2. 线性预读

     基于缓冲池中页的访问模式，而不是数量。如果一个区中的N个页都被顺序的访问了，则InnoDB会读取下一个区的所有页。

     N的值由innodb_read_ahead_threshold控制，默认值56。

哈希算法

• InnoDB中的哈希算法

  InnoDB使用哈希算法对字典进行查找，采用链表方式解决冲突、哈希函数采用除法散列方式（ ==h(k)=k mod m== ）。

  缓冲池中的Page页都有一个chain指针，指向相同哈希函数值的页。

  除法散列，m的取值为略大于2倍的缓冲池页数量的质素。