您所在的位置:首页 > 新闻中心 > MySQL索引及其背后的数据结构,TREE索引原理
公司要闻
MySQL索引及其背后的数据结构,TREE索引原理
发布时间:2020-03-16 11:16
访问量:359

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

索引使用和优化还没看

聚集索引和非聚集索引结构参考:

1.什么是索引?

磁盘IO与预读

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

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

前两天有位朋友邀请我回答个问题,为什么 MongoDB (索引)使用B-树而 Mysql 使用 B+树?我觉得这个问题非常好,从实际应用的角度来学习数据结构,没有比这更好的方法了。因为像 Mysql 和 MongoDB 这种经久考验的大型软件在设计上都是精益求精的,它们为什么选择这些数据结构?:)

索引:加速查询的数据结构。

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

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

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

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

本文从实际应用的角度来介绍以及分析B-树和B+树。

2.索引常见数据结构:

一、 二叉树

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

                                                            图片 1

 

第一次磁盘IO:

                         图片 2

 

 

 第二次磁盘IO

                           图片 3

 

第三次磁盘IO:

                             图片 4

 

第四次磁盘IO:

                                   图片 5

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

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

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


#1.顺序查找: 最基本的查询算法-复杂度O(n),大数据量此算法效率糟糕。

二、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-树由来

定义:B-树是一类树,包括B-树、B+树、B*树等,是一棵自平衡的搜索树,它类似普通的平衡二叉树,不同的一点是B-树允许每个节点有更多的子节点。B-树是专门为外部存储器设计的,如磁盘,它对于读取和写入大块数据有良好的性能,所以一般被用在文件系统及数据库中。

定义只需要知道B-树允许每个节点有更多的子节点即可。子节点数量一般在上千,具体数量依赖外部存储器的特性。

先来看看为什么会出现B-树这类数据结构。

传统用来搜索的平衡二叉树有很多,如 AVL 树,红黑树等。这些树在一般情况下查询性能非常好,但当数据非常大的时候它们就无能为力了。原因当数据量非常大时,内存不够用,大部分数据只能存放在磁盘上,只有需要的数据才加载到内存中。一般而言内存访问的时间约为 50 ns,而磁盘在 10 ms 左右。速度相差了近 5 个数量级,磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上。那么我们如何提高程序性能?减少磁盘 IO 次数,像 AVL 树,红黑树这类平衡二叉树从设计上无法“迎合”磁盘。 

图片 10

上图是一颗简单的平衡二叉树,平衡二叉树是通过旋转来保持平衡的,而旋转是对整棵树的操作,若部分加载到内存中则无法完成旋转操作。其次平衡二叉树的高度相对较大为 log n(底数为2),这样逻辑上很近的节点实际可能非常远,无法很好的利用磁盘预读(局部性原理),所以这类平衡二叉树在数据库和文件系统上的选择就被 pass 了。

空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

我们从“迎合”磁盘的角度来看看B-树的设计。

索引的效率依赖与磁盘 IO 的次数,快速索引需要有效的减少磁盘 IO 次数,如何快速索引呢?索引的原理其实是不断的缩小查找范围,就如我们平时用字典查单词一样,先找首字母缩小范围,再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快,B-树每次将范围分割为多个区间,区间越多,定位数据越快越精确。那么如果节点为区间范围,每个节点就较大了。所以新建节点时,直接申请页大小的空间(磁盘是按 block 分的,一般为 512 Byte。磁盘 IO 一次读取若干个 block,我们称为一页,具体大小和操作系统有关,一般为 4 k,8 k或 16 k),计算机内存分配是按页对齐的,这样就实现了一个节点只需要一次 IO。

图片 11

上图是一棵简化的B-树,多叉的好处非常明显,有效的降低了B-树的高度,为底数很大的 log n,底数大小与节点的子节点数目有关,一般一棵B-树的高度在 3 层左右。层数低,每个节点区确定的范围更精确,范围缩小的速度越快。上面说了一个节点需要进行一次 IO,那么总 IO 的次数就缩减为了 log n 次。B-树的每个节点是 n 个有序的序列(a1,a2,a3…an),并将该节点的子节点分割成 n+1 个区间来进行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。


#2.二叉树查找(binary tree search): O(log2n)

 三、B树的新增

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

                                 图片 12

                                     图片 13

                                     图片 14

 

漫画:什么是B+树?

B-树

图片 15

上图是一颗B-树,B-树的每个节点有 d~2d 个 key,2 这个因子指明了树的分裂及合并的规则,这个规则维持了B-树的平衡。

B-树的插入和删除就不具体介绍了,很多资料都描述了这一过程。在普通平衡二叉树中,插入删除后若不满足平衡条件则进行 旋转 操作,而在B-树中,插入删除后不满足条件则进行分裂及合并操作。

简单叙述下分裂及合并操作。

分裂:如果有一个节点有 2d 个 key,增加一个后为 2d+1 个 key,不符合上述规则 B-树的每个节点有 d~2d 个 key,大于 2d,则将该节点进行分裂,分裂为两个 d 个 key 的节点并将中值 key 归还给父节点。 
合并:如果有一个节点有 d 个 key,删除一个后为 d-1 个 key,不符合上述规则 B-树的每个节点有 d~2d 个 key,小于 d,则将该节点进行合并,合并后若满足条件则合并完成,不满足则均分为两个节点。

B-树的查找

我们来看看B-树的查找,假设每个节点有 n 个 key值,被分割为 n+1 个区间,注意,每个 key 值紧跟着 data 域,这说明B-树的 key 和 data 是聚合在一起的。一般而言,根节点都在内存中,B-树以每个节点为一次磁盘 IO,比如上图中,若搜索 key 为 25 节点的 data,首先在根节点进行二分查找(因为 keys 有序,二分最快),判断 key 25 小于 key 50,所以定位到最左侧的节点,此时进行一次磁盘 IO,将该节点从磁盘读入内存,接着继续进行上述过程,直到找到该 key 为止。

查找伪代码

Data* BTreeSearch(Root *node, Key key)
{
    Data* data;

    if(root == NULL)
        return NULL;
    data = BinarySearch(node);
    if(data->key == key)
    {
        return data;
    }else{
        node = ReadDisk(data->next);
        BTreeSearch(node, key);
    }
}

图片 16

四、B树的删除

 删除元素9:

                                  图片 17

 

                                    图片 18

码农翻身课堂讲解

B+树

B+树是B-树的变种,它与B-树的不同之处在于:

  • 在B+树中,key 的副本存储在内部节点,真正的 key 和 data 存储在叶子节点上 。
  • n 个 key 值的节点指针域为 n 而不是 n+1。

如下图为一颗B+树:

图片 19

因为内节点并不存储 data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

为了增加 区间访问性,一般会对B+树做一些优化。 
如下图带顺序访问的B+树。

图片 20


图1

五、总结

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

 

 

摘要

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

B*树:在B+树基础上,为非叶子结点也增加链表指针

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

数据结构及算法基础

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

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

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


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

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

图片 21

二分查找示意图

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

图片 22

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

二叉查找树与索引:

图片 23

二叉查找树和索引 案例

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

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

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


图片 24

 

#3.hash索引 无法满足范围查找。

计算机存储原理

B-树和B+树的区别

1.B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)。

如下所示B-树/B+树查询节点 key 为 50 的 data。

B-树

图片 25

从上图可以看出,key 为 50 的节点就在第一层,B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。


B+树

图片 26

由于B+树所有的 data 域都在根节点,所以查询 key 为 50的节点必须从根节点索引到叶节点,时间复杂度固定为 O(log n)。


2.B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

图片 27

根据空间局部性原理:如果一个存储器的某个位置被访问,那么将它附近的位置也会被访问。

B+树可以很好的利用局部性原理,若我们访问节点 key为 50,则 key 为 55、60、62 的节点将来也可能被访问,我们可以利用磁盘预读原理提前将这些数据读入内存,减少了磁盘 IO 的次数。 
当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。


3.B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

这个很好理解,由于B-树节点内部每个 key 都带着 data 域,而B+树节点只存储 key 的副本,真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的,一次磁盘 IO 会读取若干个 block,具体和操作系统有关,那么由于磁盘 IO 数据大小是固定的,在一次 IO 中,单个元素越小,量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树,从这点来看B+树相对B-树磁盘 IO 次数少。

图片 28

从上图可以看出相同大小的区域,B-树仅有 2 个 key,而B+树有 3 个 key。


#4.二叉树、红黑树 [复杂度O(h)]导致树高度非常高(平衡二叉树一个节点只能有左子树和右子树),逻辑上很近的节点(父子)物理上可能很远,无法利用局部性,IO次数多查找慢,效率低。todo 逻辑上相邻节点没法直接通过顺序指针关联,可能需要迭代回到上层节点重复向下遍历找到对应节点,效率低

1.主存存取原理

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

图片 29

主存存取原理简单示意图

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

主存的存取过程如下:

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

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

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

为什么 MongoDB 索引选择B-树,而 Mysql 索引选择B+树

这些内容了解后,我们来看为什么 MongoDB 索引选择B-树,而 Mysql (InooDB 引擎)索引选择B+树。

Mysql 大家应该比较熟悉,传统的关系型数据库,下面介绍下 MongoDB。

来看下 wiki 百科上 MongoDB 的定义:

MongoDB (from humongous) is a cross-platform document-oriented database. Classified as a NoSQL database, MongoDB eschews the traditional table-based relational database structure in favor of JSON-like documents with dynamic schemas (MongoDB calls the format BSON)

这段话的大致意思是 MongoDB 是文档型的数据库,是一种 nosql,它使用类 Json 格式保存数据。

文档型数据库和我们常见的关系型数据库不同,一般使用 XML 或 Json 格式来保存数据,归属于聚合型数据库。

键值数据库也属于聚合型数据库,熟悉 Redis 的同学应该很好理解。

举个例子:

加入我们要建立一个电子商务网站,类似淘宝这种将商品销售给用户,那么必须存储用户信息、商品目录、订单、收货地址、账单地址、付款方式等。

看下传统的关系型数据库是如何存储的:

图片 30

聚合型数据库存储模型:

图片 31

用类似 Json 的格式表示如下:

//Customer
{
        "id":1,
        "name":Tom,
        "billingAddress":[{"city":"China"}]
}

//Orders
{
        "id":99,
        "orderItem":[
                "productId"27,
                "price":100,
                "productName":book
         ],
         "shippingAddress":[{"city":"china"}],
         "orderPayment":[
            ...
        ]   
}

相对于 Mysql 关系型数据库,MongoDB 这类 nosql 适用于数据模型简单,性能要求高的场合


B-Tree 和 B+Tree数据结构:

2.磁盘存取原理

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

图片 32

硬盘:读取数据

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

为什么 MongoDB 使用B-树

MongoDB 是一种 nosql,也存储在磁盘上,被设计用在 数据模型简单,性能要求高的场合。性能要求高,看看B/B+树的区别第一点:

B+树内节点不存储数据,所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定,与 key 在树中的位置有关,最好为O(1)

我们说过,尽可能少的磁盘 IO 是提高性能的有效手段。MongoDB 是聚合型数据库,而 B-树恰好 key 和 data 域聚合在一起。


#4.B-Tree:

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

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

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

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

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

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


为什么 Mysql 使用B+树

Mysql 是一种关系型数据库,区间访问是常见的一种情况,而 B-树并不支持区间访问(可参见上图),而B+树由于数据全部存储在叶子节点,并且通过指针串在一起,这样就很容易的进行区间遍历甚至全部遍历。见B/B+树的区别第二点:

B+树叶节点两两相连可大大增加区间访问性,可使用在范围查询等,而B-树每个节点 key 和 data 在一起,则无法区间查找。

其次B+树的查询效率更加稳定,数据全部存储在叶子节点,查询时间复杂度固定为 O(log n)。

最后第三点:

B+树更适合外部存储。由于内节点无 data 域,每个节点能索引的范围更大更精确

结构:B-TREE 每个节点都是一个二元数组: [key, data],所有节点都可以存储数据。key为索引key,data为除key之外的数据。结构如下:

B-Tree和B+Tree

图片 33

1.B-Tree

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

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

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

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

图2

一个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

比如:

图片 34

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个指针(子树)

图片 35

4阶的B树

检索原理:首先从根节点进行二分查找,如果找到则返回对应节点的data,否则对相应区间的指针指向的节点递归进行查找,直到找到节点或未找到节点返回null指针。

B树的查找  查询5

图片 36

第一次磁盘IO

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

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

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

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

缺点:1.插入删除新的数据记录会破坏B-Tree的性质,因此在插入删除时,需要对树进行一个分裂、合并、转移等操作以保持B-Tree性质。造成IO操作频繁。2.区间查找可能需要返回上层节点重复遍历,IO操作繁琐。

B树的插入   插入4

图片 37

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

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

图片 38

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

B树的删除: 删除元素11

图片 39

第一步:自顶向下查找11

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

图片 40

第二步:左旋以平衡

#5.B+Tree: B-Tree的变种

B树的应用:

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


与B-Tree相比,B+Tree有以下不同点:非叶子节点不存储data,只存储索引key;只有叶子节点才存储data。结构如下图:

2.B+树

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

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

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

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

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

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

图片 41

B+树

图片 42

B+树索引

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

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

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

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

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

B+树的优势:

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

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

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

Age > =51 and age <=91


图片 43

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的大小:

图片 44

d最大值的求法

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


图3

MySQL索引实现

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

Mysql中B+Tree:在经典B+Tree的基础上进行了优化,增加了顺序访问指针。在B+Tree的每个叶子节点增加一个指向相邻叶子节点的指针,就形成了带有顺序访问指针的B+Tree。这样就提高了区间访问性能:如果要查询key为从18到49的所有数据记录,当找到18后,只需顺着节点和指针顺序遍历就可以一次性访问到所有数据节点,极大提到了区间查询效率(无需返回上层父节点重复遍历查找减少IO操作)。

MyISAM索引实现

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

图片 45

MyISAM索引原理图

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

图片 46

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表数据文件本身就是主索引。

图片 47

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

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

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

图片 48

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

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

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

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

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


图片 49

索引使用策略及优化

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

图4

3.为什么Mysql选择B+TREE索引? B+TREE索引有什么好处?

  索引本身也很大,不可能全部存储在内存中,因此索引往往以索引文件的形式存储的磁盘上。这样的话,索引查找过程中就要产生磁盘I/O消耗,相对于内存存取,I/O存取的消耗要高几个数量级,所以索引的结构组织要尽量减少查找过程中磁盘I/O的存取次数,提升索引效率。

磁盘存取原理:

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

图片 50

图5

一个磁盘由大小相同且同轴的圆形盘片组成,磁盘可以转动(各个磁盘必须同步转动)。在磁盘的一侧有磁头支架,磁头支架固定了一组磁头,每个磁头负责存取一个磁盘的内容。磁头不能转动,但是可以沿磁盘半径方向运动(实际是斜切向运动),每个磁头同一时刻也必须是同轴的,即从正上方向下看,所有磁头任何时候都是重叠的(不过目前已经有多磁头独立技术,可不受此限制)。

磁盘结构:

图片 51

图6

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

局部性原理与磁盘预读:

由于存储介质的特性,磁盘本身存取就比主存慢很多,再加上机械运动耗费,磁盘的存取速度往往是主存的几百分分之一,因此为了提高效率,要尽量减少磁盘I/O。为了达到这个目的,磁盘往往不是严格按需读取,而是每次都会预读,即使只需要一个字节,磁盘也会从这个位置开始,顺序向后读取一定长度的数据放入内存预读可以提高I/O效率。预读的长度一般为页(page:计算机管理存储器的逻辑块-通常为4k)的整倍数. 主存和磁盘以页为单位交换数据。当程序要读取的数据不在主存中时,会触发一个缺页异常,此时系统会向磁盘发出读盘信号,磁盘会找到数据的起始位置并向后连续读取一页或几页载入内存中。


B-/+Tree索引的性能优势: 一般使用磁盘I/O次数评价索引优劣。

1.结合操作系统存储结构优化处理: mysql巧妙运用操作系统存储结构(一个节点分配到一个存储页中->尽量减少IO次数) & 磁盘预读(缓存预读->加速预读马上要用到的数据).

2.B+Tree单个节点能放多个子节点相同IO次数,检索出更多信息。

3.B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。**

详解:Mysql设计利用了磁盘预读原理,将一个B+Tree节点大小设为一个页大小,在新建节点时直接申请一个页的空间,这样就能保证一个节点物理上存储在一个页里,加之计算机存储分配都是按页对齐的,这样就实现了每个Node节点只需要一次I/O操作。

B-Tree索引、B+Tree索引: 单个节点能放多个子节点,查询IO次数相同(mysql查询IO次数最多3-5次-所以需要每个节点需要存储很多数据)

B+TREE 只在叶子节点存储数据 & 所有叶子结点包含一个链指针 & 其他内层非叶子节点只存储索引数据。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。

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

B+Tree内节点去掉了data域,因此可以拥有更大的出度,拥有更好的性能。只利用索引快速定位数据索引范围,先定位索引再通过索引高效快速定位数据。

dmax=floor(pagesize/(keysize+datasize+pointsize))


Mysql 索引实现-MyISAM & InnoDB: important

**聚簇索引: 索引 和 数据文件为同一个文件。非聚簇索引: 索引 和 数据文件分开的索引。**

MyISAM & InnoDB 都使用B+Tree索引结构。但是底层索引存储不同,MyISAM 采用非聚簇索引,而InnoDB采用聚簇索引。 

MyISAM索引原理:采用非聚簇索引-MyISAMmyi索引文件和myd数据文件分离,索引文件仅保存数据记录的指针地址。叶子节点data域存储指向数据记录的指针地址。(底层存储结构: frm -表定义、 myi -myisam索引、 myd-myisam数据)

MyISAM索引按照B+Tree搜索,如果指定的Key存在,则取出其data域的值,然后以data域值-数据指针地址去读取相应数据记录。辅助索引和主索引在结构上没有任何区别,只是主索引要求key是唯一的,而辅助索引的key可以重复。MyISAM索引树如下:

图片 52

MyISAM非聚簇索引


InnoDB优势:高扩展性,充分发挥硬件性能 Crash Safe、 支持事务、 可以在线热备份

InnoDB特性:

1. 事务支持(ACID)2. 扩展性优良 3. 读写不冲突 4. 缓存加速

  1. 功能组件: redo/undo &  异步IO &  MVCC & 行级别锁 & Page Cache(LRU)

InnoDB物理存储结构如下图:

图片 53

InnoDB表空间管理

InnoDB物理存储文件结构说明:

    InnoDB以表空间Tablespace(idb文件)结构进行组织,每个Tablespace 包含多个Segment段,每个段(分为2种段:叶子节点Segment&非叶子节点Segment), 一个Segment段包含多个Extent,一个Extent占用1M空间包含64个Page(每个Page 16k),InnoDB B-Tree 一个逻辑节点就分配一个物理Page,一个节点一次IO操作。,一个Page里包含很多有序数据Row行数据,Row行数据中包含Filed属性数据等信息。

• 表空间(ibd文件)

• 段(一个索引2段:叶子节点Segment & 非叶子节点Segment

• Extent(1MB):一个Extent(1M) 包含64个 Page(16k),一个Page里包含很多有序行数据 , InnoDB B-Tree 一个逻辑节点就分配一个物理Page,一个节点一次IO操作。

• Page(16KB)

• Row

• Field

表插入数据扩展原理: 一次扩张一个Extent空间(1M),64个Page,按照顺序结构向每个page中插入顺序。

InnoDB逻辑组织结构:

图片 54

InnoDB索引树结构

每个索引一个B+树, 一个B+树节点 = 一个物理Page(16K)

• 数据按16KB切片为Page 并编号, 编号可映射到物理文件偏移(16K * N), B+树叶子节点前后形成双向链表, 数据按主键索引聚簇, 二级索引叶节点存储主键值, 通过叶节点主键值回表查找数据。

InnoDB索引原理: 

  采用聚簇索引- InnoDB数据&索引文件为一个idb文件,表数据文件本身就是主索引,相邻的索引临近存储。 叶节点data域保存了完整的数据记录(数据[除主键id外其他列data]+主索引[索引key:表主键id])。 叶子节点直接存储数据记录,以主键id为key,叶子节点中直接存储数据记录。(底层存储结构: frm -表定义、 ibd: innoDB数据&索引文件)

注:由于InnoDB采用聚簇索引结构存储,索引InnoDB的数据文件需要按照主键聚集,因此InnoDB要求表必须有主键(MyISAM可以没有)。如果没有指定mysql会自动选择一个可以唯一表示数据记录的列作为主键,如果不存在这样的列,mysql自动为InnoDB表生成一个隐含字段(6个字节长整型)作为主键。 InnoDB的所有 辅助索引 都引用 数据记录的主键 作为data域。

  聚簇索引这种实现方式使得按主键的搜索十分高效,但是辅助索引搜索需要检索两遍索引:首先检索辅助索引获得数据记录主键,然后用主键到主索引中检索获得数据记录。InnoDB聚簇索引结构:

图片 55

InnoDB聚簇索引

索引查找流程:

#1.索引精确查找: 确定定位条件, 找到根节点Page No, 根节点读到内存, 逐层向下查找, 读取叶子节点Page,通过 二分查找找到记录或未命中。(select * from user_info where id = 23)

图片 56

索引精确查找过程

#2.索引范围查找:读取根节点至内存, 确定索引定位条件id=18, 找到满足条件第一个叶节点

, 顺序扫描所有结果, 直到终止条件满足id >=22 (select * from user_info where id >= 18 and id < 22)

图片 57

索引范围查找过程

#3.全表扫描:直接读取叶节点头结点, 顺序扫描, 返回符合条件记录, 到最终节点结束

(select * from user_info where name = 'abc')

图片 58

全表扫描过程

#4.二级索引查找

图片 59

二级索引查找过程

Create table table_x(int id primary key, varchar(64) name,key sec_index(name) )

• Select * from table_x where name = “d”;

通过二级索引查出对应主键,拿主键回表查主键索引得到数据, 二级索引可筛选掉大量无效记录,提高效率

Innodb对索引的优化 Insert Buffer  todo

Innodb Buffer Pool: todo

Innodb 异步IO框架:

Innodb ACID如何保证:

•原子性 redo + undo • 一致性 redo • 隔离性 锁 + MVCC • 持久性 redo

Innodb Redo日志:

Innodb 行级别锁:

参考:

Mysql索引和查询优化