首页 > 数据库技术 > 详细

【一步一步学习mysql】Mysql索引底层数据结构与算法

时间:2018-10-11 01:03:08      阅读:58      评论:0      收藏:0      [点我收藏+]

标签:访问   范围查询   code   inno   key   每次   序列   叶子   底层   

索引是什么

  • 索引是帮助MySQL高效获取数据的排好序的数据结构。
  • 索引存储在文件里
  • 补充知识:
磁盘存取原理:
* 寻道时间(速度慢,费时)
* 旋转时间(速度较快)

磁盘IO读取效率:
* 单次IO读取是N个页的大小,读取数据量大于N个页就需要分页读取。
  • 索引的数据结构,推荐学习网站:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
    • 二叉树
      • 有可能出现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是聚集的索引实现
    • 索引和数据在同一个文件中
    • 数据的存储是建立在主键索引结构中,叶子节点是具体的数据。故必须要有主键
    • 其他索引的叶子节点是主键的值
    • 【好处】一致性和节省存储空间

【一步一步学习mysql】Mysql索引底层数据结构与算法

标签:访问   范围查询   code   inno   key   每次   序列   叶子   底层   

原文:https://www.cnblogs.com/xxxuwentao/p/9769942.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号