图片 45

2017/8/17 MySQL索引及其背后的数据结构【转载和笔记】

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

索引使用和优化还没看

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

MySQL的MyISAM、InnoDB引擎默认均使用B+树索引,本文讨论两个问题:

磁盘IO与预读

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

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

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

为什么MySQL等主流数据库选择B+树的索引结构?
如何基于索引结构,理解常见的MySQL索引优化思路?

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

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

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

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

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

为什么索引无法全部装入内存

一、 二叉树

我们先来看二叉树查找时磁盘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-树由来

定义: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)。


为什么索引无法全部装入内存?假设使用树结构组织索引,简单估算一下:

 三、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);
    }
}

假设单个索引节点12B,1000w个数据行,unique索引,则叶子节点共占约100MB,整棵树最多200MB。
假设一行数据占用200B,则数据共占约2G。

四、B树的删除

 删除元素9:

                               
  图片 16

 

                                 
  图片 17

码农翻身课堂讲解

B+树

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

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

如下图为一颗B+树:

图片 18

2017/8/17 MySQL索引及其背后的数据结构【转载和笔记】。因为内节点并不存储
data,所以一般B+树的叶节点和内节点大小不同,而B-树的每个节点大小一般是相同的,为一页。

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

图片 19


假设索引存储在内存中。也就是说,每在物理盘上保存2G的数据,就要占用200MB的内存,索引:数据的占用比约为1/10。1/10的占用比算不算大呢?物理盘比内存廉价的多,以一台内存16G硬盘1T的服务器为例,如果要存满1T的硬盘,至少需要100G的内存,远大于16G。

五、总结

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

 

 

摘要

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

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

考虑到一个表上可能有多个索引、联合索引、数据行占用更小等情况,实际的占用比通常大于1/10,某些时候能达到1/3。在基于索引的存储架构中,索引:数据的占用比过高,因此,索引无法全部装入内存。

数据结构及算法基础

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

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

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


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

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

图片 20

二分查找示意图

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

图片 21

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

二叉查找树与索引:

图片 22

二叉查找树和索引 案例

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

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

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


图片 23

 

其他结构的问题

计算机存储原理

B-树和B+树的区别

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

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

B-树

图片 24

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


B+树

图片 25

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


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

图片 26

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

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 次数少。

图片 27

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


由于无法装入内存,则必然依赖磁盘存储。而内存的读写速度是磁盘的成千上万倍,因此,核心问题是“如何减少磁盘读写次数”。

1.主存存取原理

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

图片 28

主存存取原理简单示意图

从抽象角度看,主存是一系列的存储单元组成的矩阵,每个存储单元存储固定大小的数据。每个存储单元有唯一的地址,现代主存的编址规则比较复杂,这里将其简化成一个二维地址:通过一个行地址和一个列地址可以唯一定位到一个存储单元。上图展示了一个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 的同学应该很好理解。

举个例子:

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

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

图片 29

聚合型数据库存储模型:

图片 30

用类似 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
适用于数据模型简单,性能要求高的场合


首先不考虑页表机制,假设每次读、写都直接穿透到磁盘,那么:

2.磁盘存取原理

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

图片 31

硬盘:读取数据

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

为什么 MongoDB 使用B-树

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

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

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


线性结构:读/写平均O:读/写平均O次;如果树不平衡,则最差读/写O:在BST的基础上加入了自平衡算法,读/写最大O:另一种自平衡的查找树,读/写最大O次

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

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

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

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

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

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


为什么 Mysql 使用B+树

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

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

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

最后第三点:

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

BST、AVL、RBT很好的将读写次数从O;其中,AVL和RBT都比BST多了自平衡的功能,将读写次数降到最大O。

B-Tree和B+Tree

假设使用自增主键,则主键本身是有序的,树结构的读写次数能够优化到树高,树高越低读写次数越少;自平衡保证了树结构的稳定。如果想进一步优化,可以引入B树和B+树。

1.B-Tree

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

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

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

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

B树解决了什么问题

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

比如:

图片 32

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

图片 33

4阶的B树

很多文章将B树误称为B-树,这可能是对其英文名“B-Tree”的误解。特别是与B+树一起讲的时候。想当然的认为有B+树,实际上B+树的英文名是“B+-Tree”。

B树的查找  查询5

图片 34

第一次磁盘IO

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

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

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

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

如果抛开维护操作,那么B树就像一棵“m叉搜索树”,时间复杂度为O。然而,B树设计了一种高效简单的维护操作,使B树的深度维持在约log之间,大大降低树高。

B树的插入   插入4

图片 35

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

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

图片 36

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

B树的删除: 删除元素11

图片 37

第一步:自顶向下查找11

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

图片 38

第二步:左旋以平衡

再次强调:

B树的应用:

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


不要纠结于时间复杂度,与单纯的算法不同,磁盘IO次数才是更大的影响因素。读者可以推导看看,B树与AVL的时间复杂度是相同的,但由于B树的层数少,磁盘IO次数少,实践中B树的性能要优于AVL等二叉树。

2.B+树

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

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

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

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

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

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

图片 39

B+树

图片 40

B+树索引

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

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

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

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

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

B+树的优势:

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

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

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

Age > =51 and age <=91


同二叉搜索树类似,每个节点存储了多个key和子树,子树与key按顺序排列。

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

图片 41

d最大值的求法

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


页表的目录是扩展外存+加速磁盘读写,一个页通常4K(等于磁盘数据块block的大小,见inode与block的分析),操作系统每次以页为单位将内容从磁盘加载到内存,修改页后,再择期将该页写回磁盘。考虑到页表的良好性质,可以使每个节点的大小约等于一个页,这每次加载的一个页就能完整覆盖一个节点,以便选择下一层子树;对子树同理。对于页表来说,AVL相当于1个key+2个子树的B树,由于逻辑上相邻的节点,物理上通常不相邻,因此,读入一个4k页,页面内绝大部分空间都将是无效数据。

MySQL索引实现

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

假设key、子树节点指针均占用4B,则B树节点最大m * = 8m
B;页面大小4KB。则m = 4 * 1024 / 8m =
512,一个512叉的B树,1000w的数据,深度最大 log = 3.02 ~=
4。对比二叉树如AVL的深度为log = 23.25 ~=
24,相差了5倍以上。震惊!B树索引深度竟然如此!

MyISAM索引实现

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

图片 42

MyISAM索引原理图

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

图片 43

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

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

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

另外,B树对局部性原理非常友好。如果key比较小,则除了页表的加成,缓存还能进一步预读加速。美滋滋~

InnoDB索引实现

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

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

图片 44

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

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

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

图片 45

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

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

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

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

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


B+树解决了什么问题

索引使用策略及优化

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

B树的剩余问题

然而,如果要实际应用到数据库的索引中,B树还有一些问题:

未定位数据行 无法处理范围查询

问题1

数据表的记录有多个字段,仅仅定位到主键是不够的,还需要定位到数据行。有3个方案解决:

直接将key对应的数据行存储子节点中。
数据行单独存储;节点中增加一个字段,定位key对应数据行的位置。
修改key与子树的判断逻辑,使子树大于等于上一key小于下一key,最终所有访问都将落于叶子节点;叶子节点中直接存储数据行或数据行的位置。

方案1直接pass,存储数据行将减少页面中的子树个数,m减小树高增大。

方案2的节点中增加了一个字段,假设是4B的指针,则新的m = 4 * 1024 / 12m =
341.33 ~= 341,深度最大 log = 3.14 ~= 4。

方案3的节点m与深度不变,但时间复杂度变为稳定的O。

问题2

实际业务中,范围查询的频率非常高,B树只能定位到一个索引位置,很难处理范围查询。改动较小的是2个

不改动;查询的时候先查到左界,再查到右界,然后DFS遍历左界、右界之间的节点。
在“问题1-方案3”的基础上,由于所有数据行都存储在叶子节点,B树的叶子节点本身也是有序的,可以增加一个指针,指向当前叶子节点按主键顺序的下一叶子节点;查询时先查到左界,再查到右界,然后从左界到有界线性遍历。

乍一看感觉方案1比方案2好——时间复杂度和常数项都一样,方案1还不需要改动。但是别忘了局部性原理,不管节点中存储的是数据行还是数据行位置,方案2的好处在于,依然可以利用页表和缓存预读下一节点的信息。而方案1则面临节点逻辑相邻、物理分离的缺点。

引出B+树

综上,问题1的方案2与问题2的方案1可整合为一种方案,问题1的方案3与问题2的方案2可整合为一种。实际上,数据库、文件系统有些采用了B树,有些采用B+树。

由于某些猴子暂未明白的原因,包括MySQL在内的主流数据库多选择了B+树。即:

修改key与子树的组织逻辑,将索引访问都落到叶子节点 按顺序将叶子节点串起来

B树和B+树的增、删、查过程

B树的增删过程暂时可参考从B树、B+树、B*树谈到R
树的“6、B树的插入、删除操作”小节,B+树的增删同理。此处暂不赘述。

Mysql索引优化

根据B+树的性质,很容易理解各种常见的MySQL索引优化思路。

暂不考虑不同引擎之间的区别。

优先使用自增key作为主键

前面的分析中,假设用4B的自增key作为索引,则m可达到512,层高仅有3。使用自增的key有两个好处:

自增key一般为int等整数型,key比较紧凑,这样m可以非常大,而且索引占用空间小。最极端的例子,如果使用50B的varchar,那么m
= 4 * 1024 / 54m = 75.85 ~= 76,深度最大 log = 4.43 ~=
5,再加上cache缺失、字符串比较的成本,时间成本增加较大。同时,key由4B增长到50B,整棵索引树的空间占用增长也是极为恐怖的(如果二级索引使用主键定位数据行,则空间增长更加严重)。

自增的性质使得新数据行的插入请求必然落到索引树的最右侧,发生节点分裂的频率较低,理想情况下,索引树可以达到“满”的状态。索引树满,一方面层高更低,一方面删除节点时发生节点合并的频率也较低。

优化经历:

猴子曾使用varchar的列做过主键,存储containerId,过了3、4天100G的数据库就满了,DBA小姐姐邮件里委婉表示了对我的鄙视。。。之后增加了自增列作为主键,containerId作为unique的二级索引,时间、空间优化效果相当显着。

最左前缀匹配

索引可以简单如一个列,也可以复杂如多个列,即联合索引。如果是联合索引,那么key也由多个列组成,同时,索引只能用于查找key是否存在,遇到范围查询等就不能进一步匹配了,后续退化为线性查找。因此,列的排列顺序决定了可命中索引的列数。

如有索引,查询条件a = 1 and b = 2 and c > 3 and d =
4,则会在每个节点依次命中a、b、c,无法命中d。也就是最左前缀匹配原则。

=、in自动优化顺序

不需要考虑=、in等的顺序,mysql会自动优化这些条件的顺序,以匹配尽可能多的索引列。

如有索引,查询条件c > 3 and b = 2 and a = 1 and d < 4与a = 1 and c
> 3 and b = 2 and d < 4等顺序都是可以的,MySQL会自动优化为a = 1
and b = 2 and c > 3 and d < 4,依次命中a、b、c。

索引列不能参与计算

有索引列参与计算的查询条件对索引不友好,如from_unixtime =
‘2014-05-29’。

原因很简单,如何在节点中查找到对应key?如果线性扫描,则每次都需要重新计算,成本太高;如果二分查找,则需要针对from_unixtime方法确定大小关系。

因此,索引列不能参与计算。上述from_unixtime =
‘2014-05-29’语句应该写成create_time = unix_timestamp。

能扩展就不要新建索引

如果已有索引,尽量选择修改索引。

新建索引的成本很容易理解。而基于索引的话,MySQL可以直接在索引a的B+树上,经过分裂、合并等修改为索引。

不需要建立前缀有包含关系的索引

如果已有索引,但是如果有必要,则仍然需考虑建立索引。

选择区分度高的列作索引

很容易理解。如,用性别作索引,那么索引仅能将1000w行数据划分为两部分,索引几乎无效。

区分度的公式是count /
count,表示字段不重复的比例,比例越大区分度越好。唯一键的区分度是1,而一些状态、性别字段可能在大数据面前的区分度趋近于0。

这个值很难确定,一般需要join的字段要求是0.1以上,即平均1条扫描10条记录。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持脚本之家。