Mysql索引底层数据结构与算法

索引是什么

索引是帮助MySQL高效获取数据的排好序的数据结构。
索引存储在文件里
补充知识：

磁盘存取原理：

* 寻道时间(速度慢，费时)

* 旋转时间(速度较快)

磁盘IO读取效率：

* 单次IO读取是N个页的大小，读取数据量大于N个页就需要分页读取。

索引的数据结构
- 二叉树
  - 有可能出现worst-case，如果输入序列已经排序，则时间复杂度为O(N)
- 红黑树
  - 解决了二叉树的缺点，但是在数据量大的情况下，会出现分层很深的情况，影响查询效率。
- hash
  - 查询效率很高，但是无法实现范围查询
- B树
  - 【特点】度(Degree)-节点的数据存储个数
  - 【特点】叶节点具有相同的深度
  - 【特点】叶节点的指针为空
  - 【特点】节点中的数据key从左到右递增排列
  - 【缺点】每个节点存储key+具体数据，而度涉及到IO读取，故如果度设计的很大就会影响IO读取效率。由于该限制，只能限制度的大小，使得深度无法控制。
- B+树
  - 非叶子节点不存储data，只存储key，可以增大度
  - 叶子节点不存储指针
  - 顺序访问指针，提高区间访问的性能
  - 优点
    - 一般使用磁盘I/O次数评价索引结构的优劣
    - 预读：磁盘一般会顺序向后读取一定长度的数据(页的整数倍)放入内存
    - 局部性原理：当一个数据被用到时，其附近的数据也通常会马上被使用
    - B+Tree节点的大小设为等于一个页，每次新建节点直接申请一个页的空间，这样就保证一个节点物理上也存储在一个页里，就实现了一个节点的载入只需一次I/O
    - B+Tree的度d一般会超过100，因此h非常小(一般为3到5之间)
    - 【最佳实践】使用自增的主键
      - a.自增型主键以利于插入性能的提高；
      - b.自增型主键设计(int,bigint)可以降低二级索引的空间，提升二级索引的内存命中率；
      - c.自增型的主键可以减小page的碎片，提升空间和内存的使用。

存储引擎

存储引擎是表的属性。
MyISAM是非聚集的索引实现
- 索引文件和数据文件是分开的两个文件
- 索引中叶子节点存储的是数据的地址
  - 主键索引和其他索引都是一样的，叶子节点指向的是数据文件中对应的地址
InnoDB是聚集的索引实现
- 索引和数据在同一个文件中
- 数据的存储是建立在主键索引结构中，叶子节点是具体的数据。故必须要有主键
- 其他索引的叶子节点是主键的值
- 【好处】一致性和节省存储空间

转自：https://www.cnblogs.com/xxxuwentao/p/9769942.html

巴特西

Mysql索引底层数据结构与算法

索引是什么

存储引擎

最新文章

热门文章