风也温柔

计算机科学知识库

数据库索引数据结构 你真的了解索引吗(上)?|mysql 系列(6)

  前言

  你知道索引长什么样吗?

  当磁盘剩余空间较小时,为什么我们加了索引会导致磁盘空间不足?

  为什么多加了几个索引,mysql 插入和删除的效率反而下降了呢?

  带着这些问题,我们开始今天的话题。

  什么是索引?

  索引(Index)是帮助数据库系统高效获取数据的数据结构,数据库索引本质上是以增加额外的写操作与用于维护索引数据结构的存储空间为代价的用于提升数据库中数据检索效率的数据结构。

  总结一下就是,索引就是数据结构!!一种为了提升检索效率的数据结构。

  常见的数据库的索引有:hash 表、B+树等。

  那索引物理上是怎么表现的呢?其实我们上一篇《mysql的数据到底是怎么存的(下)|mysql系列(5)》中讲到:MySQL 的存储结构分为 5 级:表空间、段、簇、页、行。创建一个索引就会创建两个段:一个数据段、一个索引段。

  InnDB的索引为什么是B+树?

  二叉树的查找效率也非常高数据库索引数据结构,比如平衡二叉树,我们在数据结构和算法中经常会用到二叉树的思想来解决问题,我们都知道mysql用的是B+树,那么为什么InnDB 不用二叉树呢?

  因为平衡二叉树这种结构在内存里面的查找效率是比较快的。但是

  索引是存在于索引文件中,是存在于磁盘中的。因为索引通常是很大的,因此无法一次将全部索引加载到内存当中数据库索引数据结构 你真的了解索引吗(上)?|mysql 系列(6),因此每次只能从磁盘中读取一个磁盘页的数据到内存中。而这个磁盘的读取的速度较内存中的读取速度而言是差了好几个级别。

  因为二叉树序列化到磁盘的时候,其物理实现是数组,具体可以参考

  《一文搞定二叉树---由二叉树到贪心算法》/post/。

  然后由于在逻辑结构上相近的节点在物理结构上可能会差很远。因此,每次读取的磁盘页的数据中有许多是用不上的。因此,查找过程中要进行许多次的磁盘读取操作。

  二叉树做索引有什么问题?

  二叉树应用在磁盘这类的搜索那么会有以下几个问题:

  这里我们复习一下几个知识点:

  磁盘IO时间:

  机械硬盘的连续读写和随机读写的性能差异:

  局部性原理与磁盘预读:

  总结一句话:由于磁盘的存储及访问的特性及二叉树的物理存储方式导致二叉树在磁盘上的查询速度很慢数据库索引数据结构,不适合做索引。

  B+树的引入

  鉴于以上几个问题, 有以下几点需要优化的:

  B树是为了充分利用磁盘预读功能来而创建的一种数据结构,也就是说B树就是为了作为索引才被发明出来的的。

  B+ 树的特点

  B+ 树的优点

  总结一下

  现在我们可以回答开头的几个问题了。

   就是一个B+树的数据结构。

  每加一个索引就会生成两个文件,所以当服务器磁盘空间少时加了索引会导致磁盘空间不足。

  索引多的话,每次添加删除数据都会维护多个文件,效率反而降低。

  本文使用 文章同步助手 同步

  文章来源:https://zhuanlan.zhihu.com/p/377721751