2017/8/17 MySQL索引及其背后的数据布局【转发和笔记】

  B-Tree就是我们常说的B树,一定不要读成B减树,否则就很丢人了。B树这种数据结构常常用于实现数据库索引,因为它的查找效率比较高。

索引使用和优化还没看

磁盘IO与预读

磁盘读取依靠的是机械运动,分为寻道时间、旋转延迟、传输时间三个部分,这三个部分耗时相加就是一次磁盘IO的时间,大概9ms左右。这个成本是访问内存的十万倍左右;正是由于磁盘IO是非常昂贵的操作,所以计算机操作系统对此做了优化:预读;每一次IO时,不仅仅把当前磁盘地址的数据加载到内存,同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明:当访问一个地址数据的时候,与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页(page)。一页的大小与操作系统有关,一般为4k或者8k。这也就意味着读取一页内数据的时候,实际上发生了一次磁盘IO。

归纳要点:索引是数据结构。为什么使用索引,从计算机存储原理去考虑——胖树-(B树和B+树)。B树的原理,结合计算机存储原理知道了为什么B树性能好。MySQL中MyISAM和InnoDB都使用了B+树,有什么不同(聚集索引和非聚集索引),辅助索引有什么不同。

B-Tree与二叉查找树的对比

  我们知道二叉查找树查询的时间复杂度是O(logN),查找速度最快和比较次数最少,既然性能已经如此优秀,但为什么实现索引是使用B-Tree而不是二叉查找树,关键因素是磁盘IO的次数。

数据库索引是存储在磁盘上,当表中的数据量比较大时,索引的大小也跟着增长,达到几个G甚至更多。当我们利用索引进行查询的时候,不可能把索引全部加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页就对应索引树的节点。

根据原理得出索引的使用和优化(这个还没看)

一、 二叉树

我们先来看二叉树查找时磁盘IO的次:定义一个树高为4的二叉树,查找值为10:

                                         
               
  图片 1

 

第一次磁盘IO:

                       
 图片 2

 

 

 第二次磁盘IO

                         
 图片 3

 

第三次磁盘IO:

                           
 图片 4

 

第四次磁盘IO:

                                 
 图片 5

从二叉树的查找过程了来看,树的高度和磁盘IO的次数都是4,所以最坏的情况下磁盘IO的次数由树的高度来决定。

从前面分析情况来看,减少磁盘IO的次数就必须要压缩树的高度,让瘦高的树尽量变成矮胖的树,所以B-Tree就在这样伟大的时代背景下诞生了。

转载和笔记:MySQL索引背后的数据结构及算法原理

二、B-Tree

m阶B-Tree满足以下条件:

1、每个节点最多拥有m个子树

2、根节点至少有2个子树

3、分支节点至少拥有m/2颗子树(除根节点和叶子节点外都是分支节点)

4、所有叶子节点都在同一层、每个节点最多可以有m-1个key,并且以升序排列

 如下有一个3阶的B树,观察查找元素21的过程:

                                         
                                 
  图片 6

第一次磁盘IO:     

                                         
               
 图片 7

第二次磁盘IO:

                                         
     
  图片 8

这里有一次内存比对:分别跟3与12比对

第三次磁盘IO:

                                         
         
 图片 9

这里有一次内存比对,分别跟14与21比对

从查找过程中发现,B树的比对次数和磁盘IO的次数与二叉树相差不了多少,所以这样看来并没有什么优势。

但是仔细一看会发现,比对是在内存中完成中,不涉及到磁盘IO,耗时可以忽略不计。另外B树种一个节点中可以存放很多的key(个数由树阶决定)。

相同数量的key在B树中生成的节点要远远少于二叉树中的节点,相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后,性能的差异就显现出来了。

漫画:什么是B-树?

 三、B树的新增

在刚才的基础上新增元素4,它应该在3与9之间:

                               
 图片 10

                                   
 图片 11

                                   
 图片 12

 

漫画:什么是B+树?

四、B树的删除

 删除元素9:

                               
  图片 13

 

                                 
  图片 14

码农翻身课堂讲解

五、总结

  插入或者删除元素都会导致节点发生裂变反应,有时候会非常麻烦,但正因为如此才让B树能够始终保持多路平衡,这也是B树自身的一个优势:自平衡;B树主要应用于文件系统以及部分数据库索引,如MongoDB,大部分关系型数据库索引则是使用B+树实现。

 

 

摘要

MySQL数据库支持多种所应类型,如Btree索引,哈希索引,全文索引等等。BTree索引,平常使用MySQL时主要打交道的索引。

数据结构及算法基础

索引是什么:索引(Index)是帮助MySQL高效获取数据的数据结构。索引本质:数据结构。

为什么需要索引:使查询数据的速度尽可能快。

怎么快:从查询算法角度优化。常见的查询算法如下:


顺序查找
:顺序地检查列表的每个元素,直到找到与目标值匹配的元素。如果算法到达列表的末尾,搜索将失败。
时间复杂度:O(n)

二分查找:时间复杂度O(log N)  局限性:要求被检索数据有序

图片 15

二分查找示意图

二叉树查找:局限性
同样的一组数据,输入的顺序不同,二叉树的高度不同,太高的树可能有太多的IO操作。

图片 16

一组数据用不同的输入顺序得到不同的二叉查找树

二叉查找树与索引:

图片 17

二叉查找树和索引 案例

上图展示了一种可能的索引方式。左边是数据表,一共有两列六条记录,最左边的是数据记录的物理地址(注意逻辑上相邻的记录在磁盘上也并不是一定物理相邻的)。为了加快Age的查找,可以维护一个右边所示的二叉查找树,每个节点分别包含索引键值和一个指向对应数据记录物理地址的指针,这样就可以运用二叉查找在O(log2n)的复杂度内获取到相应数据。

虽然这是一个货真价实的索引,但是实际的数据库系统几乎没有使用二叉查找树或其进化品种红黑树(red-black
tree)实现的,原因与IO操作有关。

Select * from users where age >= 24 and age <=93
 (范围查找无法解决)


计算机存储原理

1.主存存取原理

目前计算机使用的主存基本都是随机读写存储器(RAM),现代RAM的结构和存取原理比较复杂,转载博客抛却具体差别,抽象出一个十分简单的存取模型来说明RAM的工作原理。

图片 18

主存存取原理简单示意图

从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。上图展示了一个4
x 4的主存模型。

主存的存取过程如下:

当系统需要读取主存时,则将地址信号放到地址总线上传给主存,主存读到地址信号后,解析信号并定位到指定存储单元,然后将此存储单元数据放到数据总线上,供其它部件读取。

写主存的过程类似,系统将要写入单元地址和数据分别放在地址总线和数据总线上,主存读取两个总线的内容,做相应的写操作。

这里可以看出,主存存取的时间仅与存取次数呈线性关系,因为不存在机械操作,两次存取的数据的“距离”不会对时间有任何影响,例如,先取A0再取A1和先取A0再取D3的时间消耗是一样的。

2.磁盘存取原理

上文说过,索引一般以文件形式存储在磁盘上,索引检索需要磁盘I/O操作。与主存不同,磁盘I/O存在机械运动耗费,因此磁盘I/O的时间消耗是巨大的。

图片 19

硬盘:读取数据

当需要从磁盘读取数据时,系统会将数据逻辑地址传给磁盘,磁盘的控制电路按照寻址逻辑将逻辑地址翻译成物理地址,即确定要读的数据在哪个磁道哪个扇区。为了读取这个扇区的数据,需要将磁头放到这个扇区上方,为了实现这一点,磁头需要移动对准相应磁道,这个过程叫做寻道,所耗费时间叫做寻道时间,然后磁盘旋转将目标扇区旋转到磁头下,这个过程耗费的时间叫做旋转时间

3.局部性原理与磁盘预读

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存。这样做的理论依据是计算机科学中著名的局部性原理:

当一个数据被用到时,其附近的数据也通常会马上被使用。

程序运行期间所需要的数据通常比较集中。

由于磁盘顺序读取的效率很高(不需要寻道时间,只需很少的旋转时间),因此对于具有局部性的程序来说,预读可以提高I/O效率。

预读的长度一般为页(page)的整倍数。页是计算机管理存储器的逻辑块,硬件及操作系统往往将主存和磁盘存储区分割为连续的大小相等的块,每个存储块称为一页(在许多操作系统中,页得大小通常为4k),主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中,然后异常返回,程序继续运行。


B-Tree和B+Tree

1.B-Tree

参考:漫画:什么是B-树?

B-树就是B树,不是B减树

磁盘IO次数等于索引树的高度,为了减少磁盘IO次数,因此需要一个更胖的“二叉查找树”

B树:一种多路平衡查找树,它的每一个节点最多包含k个孩子,k称为B树的阶。k的大小取决于磁盘页的大小。

一个m阶的B-Tree定义:

 (1)树中每个结点至多有m棵子树;  

 (2)若根结点不是叶子结点,则至少有两棵子树;  

 (3)除根之外的所有非终端结点至少有ceil(m/2)棵子树;  

 (4)所有的非终端结点中包含下列信息数据 

             (n, A0, K1, A1, K2, A2, …, Kn, An)     即n个关键字,
n+1个指针

             Key 是有序的, k1<k2<…Kn

比如:

图片 20

4阶B-Tree

(1) 树中每个结点至多有4棵子树;

(2) 若根结点不是叶子结点,则至少有两棵子树; 

(3) 除根之外的所有非终端结点至少有ceil(m/2) = 2棵子树;  

(4) 所有的非终端结点中包含下列信息数据 

(3, A0, K1, A1,K2, A2,K3,A3)   即3个 key , 4个指针(子树)

(2, A0, K1, A1,K2, A2,)  即2个 key , 3个指针(子树)

(1, A0, K1, A1)  即1个 key , 2个指针(子树)

图片 21

4阶的B树

B树的查找  查询5

图片 22

第一次磁盘IO

 在内存中定位(和9比较,后面提到根节点常驻内存)

第二次磁盘IO:转入【2  6】, 在内存中定位(和2 6比较)

第三次磁盘IO:转入【3 5】,在内存中定位(和3 5比较)

比较操作并不比二叉查找树少,但IO操作少,如果单一节点元素多(不能超过磁盘页的大小),比较都发生在内存中,内存中的比较耗时与IO操作相比几乎可以忽略。只要树的高度足够低,IO次数足够少,查找性能就能提高。

B树的插入   插入4

图片 23

第一步:4应该插入到3和5之间

分析:节点3 5无法增加,节点2
6无法增加元素,根节点9可以增加元素,升级为两元素节点。2比4小,6在4和9之间,于是拆分2和6,得到:

图片 24

第二步:拆分节点3,5与节点2,6,让根节点9升级为两元素节点49。节点6独立为根节点的第二个孩子

B树的删除: 删除元素11

图片 25

第一步:自顶向下查找11

删除11后,12只有1个孩子,不符合B树规范。因此找出12,13,15三个节点的中位数13,取代节点12,而节点12自身下移成为第一个孩子。(这个过程称为左旋

图片 26

第二步:左旋以平衡

B树的应用:

应用于文件系统以及部分数据库索引。比如著名的非关系型数据库MongoDB。


2.B+树

参考:漫画:什么是B+树?

定义:B+ Tree是应文件系统需求所产生一个一种B Tree的变种,

 一颗m阶的B+Tree和m阶的B-Tree ,主要差别在于:

(1)有n棵子树的节点有n个key (而不是n-1个)

(2)所有叶子节点包含了全部的key,
以及指向相关记录的指针。叶子节点本身也会依照key自小而大链接起来

(3)所有中间节点都可以看做是索引部分,节点中仅仅含有子树的最小/最大的key,
但是不再保存数据

图片 27

B+树

图片 28

B+树索引

补充:B树与B+树中的另一个区别:“卫星数据”的位置。

卫星数据:索引元素所指向的数据记录,比如数据库中的某一行。在B树中,无论中间节点还是叶子节点都带有卫星数据。

补充:在数据库的聚集索引(Clustered
Index)中,叶子节点直接包含卫星数据。在非聚集索引(NonClustered
Index)中,叶子节点带有指向卫星数据的指针。

聚集索引:一种索引,该索引中键值的逻辑顺序决定了表中相应行的物理顺序。

非聚集索引:一种索引,该索引中索引的逻辑顺序与磁盘上行的物理存储顺序不同。

B+树的优势:

(1)节点可以存放更多的key

因为key 对于的数据地址只存放在叶子节点

(2)查询一个范围内的数据更有效

Age > =51 and age <=91


B树索引性能分析

上文说过一般使用磁盘I/O次数评价索引结构的优劣。先从B-Tree分析,根据B-Tree的定义,可知检索一次最多需要访问h个节点。数据库系统的设计者巧妙利用了磁盘预读原理,将一个节点的大小设为等于一个页,这样每个节点只需要一次I/O就可以完全载入

为了达到这个目的,在实际实现B-Tree还需要使用如下技巧:

每次新建节点时,直接申请一个页的空间,这样就保证一个节点物理上也存储在一个页里,加之计算机存储分配都是按页对齐的,就实现了一个node只需一次I/O。

B-Tree中一次检索最多需要h-1次I/O(根节点常驻内存)渐进复杂度为O(h)=O(logdN)。一般实际应用中,出度d是非常大的数字,通常超过100,因此h非常小(通常不超过3)。

综上所述,用B-Tree作为索引结构效率是非常高的。

而红黑树这种结构,h明显要深的多。由于逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,所以红黑树的I/O渐进复杂度也为O(h),效率明显比B-Tree差很多。

上文还说过,B+Tree更适合外存索引,原因和内节点出度d有关。从上面分析可以看到,d越大索引的性能越好,而出度的上限取决于节点内key和data的大小:

图片 29

d最大值的求法

floor表示向下取整。由于B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。


MySQL索引实现

在MySQL中,索引属于存储引擎级别的概念,不同存储引擎对索引的实现方式是不同的,本文主要讨论MyISAM和InnoDB两个存储引擎的索引实现方式。

MyISAM索引实现

MyISAM引擎使用B+Tree作为索引结构叶节点的data域存放的是数据记录的地址。下图是MyISAM索引的原理图:

图片 30

MyISAM索引原理图

这里设表一共有三列,假设我们以Col1为主键,则图8是一个MyISAM表的主索引(Primary
key)示意。可以看出MyISAM的索引文件仅仅保存数据记录的地址。在MyISAM中,主索引和辅助索引(Secondary
key)在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。如果我们在Col2上建立一个辅助索引,则此索引的结构如下图所示:

图片 31

MyISAM辅助索引data域存储的是数据记录的地址

同样也是一颗B+Tree,data域保存数据记录的地址。因此,MyISAM中索引检索的算法为首先按照B+Tree搜索算法搜索索引,如果指定的Key存在,则取出其data域的值,然后以data域的值为地址,读取相应数据记录。

MyISAM的索引方式也叫做“非聚集”的,之所以这么称呼是为了与InnoDB的聚集索引区分。

InnoDB索引实现

虽然InnoDB也使用B+Tree作为索引结构,但具体实现方式却与MyISAM截然不同。

第一个重大区别是InnoDB的数据文件本身就是索引文件。从上文知道,MyISAM索引文件和数据文件是分离的,索引文件仅保存数据记录的地址。而在InnoDB中,表数据文件本身就是按B+Tree组织的一个索引结构,这棵树的叶节点data域保存了完整的数据记录。这个索引的key是数据表的主键,因此InnoDB表数据文件本身就是主索引。

图片 32

InnoDB主索引(也是数据文件)

上图是InnoDB主索引(同时也是数据文件)的示意图,可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集,所以InnoDB要求表必须有主键(MyISAM可以没有),如果没有显式指定,则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键,如果不存在这种列,则MySQL自动为InnoDB表生成一个隐含字段作为主键,这个字段长度为6个字节,类型为长整形。

第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说,InnoDB的所有辅助索引都引用主键作为data域。例如,图11为定义在Col3上的一个辅助索引:

图片 33

InnoDB的辅助索引data域是对应的主键

这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得主键,然后用主键到主索引中检索获得记录。

了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助,例如知道了InnoDB的索引实现后,就很容易明白

(1)为什么不建议使用过长的字段作为主键,因为所有辅助索引都引用主索引,过长的主索引会令辅助索引变得过大。

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


索引使用策略及优化

MyISAM的索引文件仅仅保存数据记录的地址

相关文章