索引

MySQL索引背后的数据结构及算法原理 数据库索引，到底是什么做的？

索引的本质

索引（Index）是帮助MySQL高效获取数据的数据结构

数据库索引为什么使用B+树？ 为什么不是Hash,B树

1. Hash(O(1))比树(O(log(n))),增删改查都快,但是不适合SQL语句,(InnoDB并不支持哈希索引)
2. 二叉搜索树: 1)当数据量大的时候，树的高度会比较高，数据量大的时候，查询会比较慢,2)每个节点只存储一个记录，可能导致一次查询有很多次磁盘IO
3. B树,B-树(m叉搜索): 叶子节点，非叶子节点，都存储数据；中序遍历,获取所有节点,但是节点存放数据,依次I/O获取的数据比B+Tree少,增加I/o次数
4. B+树: 1)非叶子节点不再存储数据，数据只存储在同一层的叶子节点上 2)增加了顺序访问指针变种的B+Tree,叶子之间，增加了链表，获取所有节点，不再需要中序遍历 3)适合范围查找
5. 索引也很大,不能存储在内存,存储在磁盘,涉及到磁盘IO,树的高度越高,磁盘io开销越大,所以需要降低树的高度,这就是二叉树不如多叉树的原因

什么是局部性原理？

1. 内存读写快，磁盘读写慢，而且慢很多
2. 磁盘预读：磁盘读写并不是按需读取，而是按页预读，一次会读一页的数据(4k)，每次加载更多的数据，如果未来要读取的数据就在这一页中，可以避免未来的磁盘IO，提高效率
3. 局部性原理：软件设计要尽量遵循“数据读取集中”与“使用到一个数据，大概率会使用其附近的数据”，这样磁盘预读能充分提高磁盘IO,B+Tree增加的顺序访问可满足

聚集索引和非聚集索引

指叶子节点存的是全部数据,还是数据指向

唯一索引 与 普通索引

1. 查询:普通索引和唯一索引一样,都是读取磁盘页,普通索引需要遍历查到值后面的范围是否也满足,开销很小
2. 插入:普通索引,插入buffer,然后返回,唯一索引 需要将数据页读到内存,查看是否有冲突,开销大

前缀索引

为什么需要前缀索引:索引越长,占用的磁盘空间就越大，相同的数据页能放下的索引值就越少,搜索效率会很低

考虑因素:是否需要覆盖索引

#计算前缀索引,多少合适
mysql> select count(distinct email) as L from user;
mysql> select 
  count(distinct left(email,4)）as L4,
  count(distinct left(email,5)）as L5,
  count(distinct left(email,6)）as L6,
  count(distinct left(email,7)）as L7,
from user;

覆盖索引、前缀索引、索引下推

覆盖索引优化

#id 主键 k 普通index
select * from test where k between 3 and 5; #需要回表
select id from test where  k between 3 and 5; #id已经在普通索引上查到,不需要回表

前缀索引

select * from test where name like "张%"

索引下推

mysql> select * from tuser where name like '张 %' and age=10 and ismale=1;
#InnoDB 在 (name,age) 索引内部就判断了 age是否等于10,如不满足就不回表

为什么innodb的主键不适合使用非递增主键

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

在索引上做函数操作,会破坏索引值的有序性