亲宝软件园·资讯

展开

Mysql数据库索引简介

熊猫编程 人气:2

什么是索引?

  索引是帮助高效获取数据的数据结构,避免全表扫描

 

mysql为什么用B+TREE作索引?而不是其它树形 结构?比如B树?

  尽量少地访问资源是数据库设计的重要原则之一。

  B树不管叶子节点还是非叶子节点,都会保存数据,这样导致在非叶子节 点中能保存的指针数量变少(有些资料也称为扇出),指针少的情况下要保 存大量数据,只能增加树的高度,导致IO操作变多,查询性能变低;

mysql索引如何实现?

  

   我们先将数据记录按主键进行排序,分别存放在不同的页中(为了便于理解 我们这里一个页中只存放3条记录,实际情况可以存放很多),除了存放数据 的页以外,还有存放键值+指针的页,如图中page number=3的页,该页存放 键值和指向数据页的指针,这样的页由N个键值+指针组成。当然它也是排好 序的。这样的数据组织形式,我们称为索引组织表。

  1、InnoDB存储引擎的最小存储单元是页,页可以用于存放数据也可以用于 存放键值+指针,在B+树中叶子节点存放数据,非叶子节点存放键值+指针。

  2、索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中, 进而在去数据页中查找到需要的数据;

什么是回表?

   现在,我们一起来看看这条SQL查询语句的执行流程:

  1. 在k索引树上找到k=3的记录,取得 ID = 300;

  2. 再到ID索引树查到ID=300对应的R3;

  3. 在k索引树取下一个值k=5,取得ID=500;

  4. 再回到ID索引树查到ID=500对应的R4;

  5. 在k索引树取下一个值k=6,不满足条件,循环结束。

  在这个过程中,回到主键索引树搜索的过程,我们称为回表。

  可以看到,这个查询过程读了k 索引树的3条记录(步骤1、3和5),回表了两次(步骤2和4)。 在这个例子中,由于查询结果所需要的数据只在主键索引上有,所以不得不回表。

什么是覆盖索引?

  避免回表过程

  如果执行的语句是select ID fromTwhere k between 3 and 5,这时只需要查ID的值,而ID的值 已经在k索引树上了,因此可以直接提供查询结果,不需要回表。也就是说,在这个查询里面, 索引k已经“覆盖了”我们的查询需求,我们称为覆盖索引。

Msql5.6引入的索引下推优化

  MySQL 5.6 引入的索引下推优化(index condition pushdown), 可以在索引遍历过程中,对索 引中包含的字段先做判断,直接过滤掉不满足条件的记录,减少回表次数。

  

  无索引下推优化

 

  

   索引下推优化

  每个虚线箭头表示一次回表

 

为什么删除了表的部分记录,它的索引还在?

  alter table T engine=InnoDB

 

B+树在线模拟

https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html

  

 

InnoDB一棵B+树可以存放多少行数据?

  在计算机中磁盘存储数据最小单元是扇 区,一个扇区的大小是512字节,而文件系统(例如XFS/EXT4)他的最小单 元是块,一个块的大小是4k,而对于我们的InnoDB存储引擎也有自己的最小 储存单元——页(Page),一个页的大小是16K。

  文件系统中一个文件大小只有1个字节,但不得不占磁盘上4KB的空间。

  

 

  1、InnoDB存储引擎的最小存储单元是页,页可以用于存放数据也可以用于 存放键值+指针,在B+树中叶子节点存放数据,非叶子节点存放键值+指针。

  2、索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中, 进而在去数据页中查找到需要的数据;

 

  单个叶子节点(页)中的记录数=16K/1K=16。(这里假设 一行记录的数据大小为1k,实际上现在很多互联网业务数据记录大小通常就 是1K左右)。

  那么现在我们需要计算出非叶子节点能存放多少指针,其实这也很好算,我 们假设主键ID为bigint类型,长度为8字节,而指针大小在InnoDB源码中设置 为6字节,这样一共14字节,我们一个页中能存放多少这样的单元,其实就代 表有多少指针,即16384/14=1170。

  那么可以算出一棵高度为2的B+树,能存 放1170*16=18720条这样的数据记录。 根据同样的原理我们可以算出一个高度为3的B+树可以存放: 1170*1170*16=21902400条这样的记录。所以在InnoDB中B+树高度一般为1- 3层,它就能满足千万级的数据存储。

  在查找数据时一次页的查找代表一次 IO,所以通过主键索引查询通常只需要1-3次IO操作即可查找到数据。

怎么得到InnoDB主键索引B+树的高度?

 

加载全部内容

相关教程
猜你喜欢
用户评论