为什么磁盘存储引擎用b+树来作为索引结构？

宝玉水果

文末有端午福利。作者：jaydenwen，腾讯PCG后台开发工程师在数据库或者存储的世界里，存储引擎的角色一直处于核心位置。往简单了说，存储引擎主要负责数据如何读写。往复杂了说，怎么快速、高效的完成数据的读写，一直是存储引擎要解决的关键问题。在绝大部分介绍、讲解存储引擎的书籍或者文章里，大家都默认了读多写少的磁盘存储引擎采用的就是b+树，而极少有人来剖析选择b+树作为索引结构的背后，到底有着怎样的思考和权衡？为了解答上述问题，本文尝试从一个新的视角和大家讨论：在处理读多写少的场景下，为什么基于磁盘的存储引擎会选择用b+树来作为索引结构？希望在看完本文后，读者能对该问题有一个全新的认识和属于自己的答案。限于个人能力有限，有表述、理解不正当之处希望批评指正。本文的内容主要以问答方式展开，层层递进分析、解决问题，本文涉及内容会围绕下面三个问题展开。在开始阅读本文内容前，大家不妨先尝试自己回答下面三个问题！为了减少读者的疑惑，在开始本文的正式内容之前，先和读者做一些简要的关键名词的解释和说明：1.存储引擎：存储引擎是一个很广的范畴，有处理读多写少的基于页结构的b+树存储引擎，也有后起之秀基于日志结构(lsm树)的存储引擎。在本文中提到的存储引擎，如没有特殊说明，都指的是针对处理读多写少场景的基于磁盘的b+树存储引擎，这类存储引擎在关系型数据库中出现的频率较高，经典代表就是mysql中的innodb，此外golang编写的boltdb也属于本文讨论的范畴。2.扩展内容：文中标识为扩展内容的章节，对于基础相对较好的读者这些内容可以选择性阅读，不读也不会造成本文核心内容理解困难；对于基础相对一般的小伙伴，可以选择性的进行阅读。下面我们先尝试回答前两个问题，因为前两个问题可以算作是一大类问题。第一个问题主要在于数据结构的选型。第二个问题主要在于因果关系的区分。1.背景这个问题的答案，我们从哪里开始说起呢？想之又想，只有搞清楚了整体的一个背景，我们才能知道当时的工程师面临的怎样的一个问题。近而，我们才能尝试从根上解释这个问题。从整体的大的环境来看，他们要解决的问题主要面临的以下四个主要特点：1.处理读多写少的场景2.关系型数据库按照行组织3.存储千万级量级数据4.采用性价比高的存储接下来我们一一对其进行解释，因为如果上述四个背景如果不成立的话，说明我们一开始的出发点就错了，后面的回答都是无稽之谈。1.1处理读多写少的场景提起这个话题，我们就不得不说，在互联网发展起来的早期，大部分的系统主要处理的是读多写少的场景。例如早期的bbs内容、博客、门户网站、电商的商品入库等等，这些场景都可以划分为读多写少。他们通过有限次的写操作将数据写入到数据库中，然后供用户多次浏览、阅读。发展到今天的互联网，面向用户的很多系统仍然是属于读多写少的范畴。所以读多写少这是一个早期存储引擎在数据读写时面临的最大的背景。1.2关系型数据库按照行组织早期的时候存储引擎这个概念主要还是出现在关系型数据库中，大部分人接触这个概念估计也是因为mysql，mysql中经常提到存储引擎这个词。在关系型数据库中，数据往往通过数据库->表(多列)-->行的方式来组织。最终落到存储引擎这一层时，数据已经按照行的格式来组织了。广义来看其实也就是类似于key-value的存储了，只不过在关系型数据库中，到达存储引擎这层的value是一行记录按照指定的格式来扁平化组织而成，具体的格式大同小异。这儿不再展开赘述。大家可以自行搜索资料查阅，此处主要是抛出来在关系型数据库中数据按照行格式来存储这个背景。为了方便介绍，在后续的内容中，存储引擎存储的数据我们就统一按照key-value来讨论了。此处的key大家暂且可以直观的理解为主键。1.3存储千万级量级数据随着互联网的迅速发展，数据存储的量级日益增长，很快就达到了存储千万级量级数据这个量级。很明显这个背景从需求的角度看，其实是属于不断迭代的过程。不可能初期互联网一起来，马上就面临这个量级。但是我们也知道在计算机软件的世界中，可扩展性是大家耳熟能详的词语。所以在设计存储引擎时，自然而然肯定会考虑这个问题。所以此处，我们将存储千万级数据量级这个作为第三个背景。1.4采用性价比高的存储接着第三个背景，自然而然就引出了数据存储在哪里的问题。回答这个问题，必须就得引出一个成本问题了。如果不考虑成本来存储，那自然问题就简化了。但是千万级量级的数据存储时，有了成本的限制，就得思考了。我们的目标是要找到一个成本相对廉价，但又能支持千万级数据量级的存储介质。对于计算机中，存储数据的媒介整体可以分为两大类：1.易失性存储：典型代表内存2.非易失性存储：典型代表硬盘(磁盘)，尤其是早期的机械硬盘关于二者的详细对比，大家可以参考下图：首先，通过上图的对比，我们大致可以确定了，我们期望的存储介质就是硬盘(主要是机械硬盘)了。因为它很符合我们所寻找的几个特点。但我们都知道硬盘虽然符合我们的要求，但硬盘有着它先天结构的限制。访问磁盘的速度要比访问内存慢的多。到这儿也就不得不提一下，关于机械硬盘它的构成了。关于机械硬盘的简单介绍，我们在下面的扩展内容中进行简要介绍，大家感兴趣可以进行阅读，已经掌握的读者可以直接跳过这部分虚线框中的内容。扩展内容上图关于磁盘介绍的摘自本篇文章。普通的机械硬盘读写数据主要是通过移动磁头到对应的磁道，然后再旋转磁头到对应的扇区。最后进行移动磁头进行读写数据。简单说：一次硬盘数据读写主要包括三大部分耗时：寻道时间、旋转时间、传输时间。而在这其中寻道时间主要占大头，主要是因为磁头的移动主要是马达通过驱动磁臂近而移动磁头，这个运动属于机械运动，所以速度相对较慢。对磁盘而言，磁盘的访问肯定是要比内存慢的。但是在磁盘访问时，又有两种访问方式：1.随机IO2.顺序IO顺序IO的访问速度要远远快于随机IO，其根本原因是：顺序IO主要减少了磁头的移动频率，也就是减少了寻道时间。所以它的性能要比随机IO要快很多。由于篇幅有限，关于硬盘的介绍我们就不过多展开了，不然就跑题了。有了上述的知识，我们就足以开展我们后续的内容了。关于硬盘的详细内容介绍，大家可以自行找其他资料学习或者点击本篇文章进行阅读。下面我们继续介绍我们的主要内容。其次，我们既然选择了硬盘做存储媒介，那就必须想办法克服这个问题。下面这张图详细描述了内存访问速度和磁盘访问速度的对比结果。下面我们简单总结下，抛出我们在这块得出的结论：结论1可以参考扩展内容详细了解。1.磁盘访问时间：寻道时间+旋转时间+传输时间：寻道时间：8ms~12ms旋转时间：7200转/min：半周4ms传输时间：50M/s，约0.3ms2.磁盘随机IO≪磁盘顺序IO≈内存随机IO≪内存顺序IO3.机械磁盘和固态硬盘构成：机械硬盘：电磁存储，通过电磁信号转变来控制读写，磁头机械臂移动固态硬盘：半导体存储，用固态电子存储芯片阵列、由控制单元和存储单元组成，内部由闪存颗粒组成。速度较1.5总结本节主要交代了4个大的背景，下面再和大家回顾一下。1.处理读多写少的场景2.关系型数据库按照行组织3.存储千万级量级数据4.采用性价比高的存储最后我们结合实际的场景选择以硬盘这种介质来存储数据，同时在存储引擎层，数据按照抽象层面的key-value来组织读取和写入。了解了大的背景，下面得了解我们的目标是啥了。没有目标就没有方向，搞清楚目标对我们至关重要。2.目标在第一节中，我们介绍了四大基本背景。并分析出来了我们最终需要采取硬盘来存储数据。在本节中，我们将重点关注我们的要达到的目标，只有明确了目标，我们才能更好的进行自顶向下分解任务并解决问题。在介绍我们的目标前，我们先来看看我们在基于磁盘存储数据的条件下，一次常规的用户请求大概是怎样的？2.1常规的一次用户请求响应过程我们都知道，我们的数据存储在硬盘上，因此当用户的请求(读/写)进来后，首先会到操作系统管理的内存中，在内存中进行一些逻辑处理，然后cpu会发送指令从硬盘读取数据到内存中，最后就会响应上层用户(读：读取的数据、写：写数据是否成功等)。上面描述的一个大概的流程。从中我们可以看到整个过程经历三个阶段：请求过程：用户请求->内存->硬盘响应过程:响应用户O(logn)->O(n)->...由快到慢的一个对比结果。我们都知道互联网的应用中，排序、范围查找是一个再普遍不过的需求了。例如在电商网站购物时，大部分用户都会下意识的点击按照销量从高到低排序；再比如在门户新闻网站上，我们会关注过去一周某个新闻被阅读的次数，按照时间来排序；再比如推荐系统中，我们会按照内容的一类或者多类属性对物品进行排序，还有很多很多例子。所以我们在选择数据结构时，必须考虑支持范围查找、排序等操作。基于这点的话，看来哈希表就不太符合我们的需求了。那我们退而求其次，再来看看O(logn)的时间复杂度中，我们选择哪种数据结构呢？这几种数据结构粗略一看貌似都能满足我们的需求，同时上述几种数据结构:二叉查找/排序树(bsttree)、平衡二叉树(avltree)、红黑树(rbtree)、b树(b/b-tree)、b+树(b+tree)、跳表(skiplist)在内存中都可以实现，我们如何选择呢？直观来看我们选哪种好像都可以，但我们别忘了，我们的数据最终要落到硬盘，既然这儿得不出结论，那我们就从硬盘的维度来看看，硬盘上哪种数据结构好维护呢？3.2目光转向磁盘根据前面的介绍，我们的数据流向分为三个阶段，以读取操作举例：磁盘->内存->用户。既然这样的话，我们的直观想法是，如果能在内存和硬盘这两种介质上维护同一种数据结构，那就最完美了，这样当用户请求进来后，从磁盘加载数据后，可以直接加载到内存中，然后做一些处理就返回用户了。如果直观想法走不通的话(找不到这样一种数据结构)。那我们就只能按照间接思路来出发了，硬盘上维护一种数据结构存储我们的数据，内存中选择另外一种数据结构保存数据。当从硬盘读取数据到内存中时，中间做一层转换。间接思路这种做法是下策，因为中间数据的转换避免不了会引入一些性能的损耗。那就先按照直观想法出发来找找看，是否存在这样一类数据结构呢？3.3直观思路出发我们先想想，既然我们的目标仍然是快速、高效读写，那对应到磁盘上，怎么做到对磁盘快速、高效读写呢？根据前面的铺垫介绍，大伙应该都知道了那就尽可能的利用磁盘的顺序IO呗。提到顺序IO，脑子里第一时间蹦出来的自然就是追加写，因为这种方式就是一种典型的顺序写、顺序IO，性能挺高的。我们假设用户每个写请求进来，都采用追加写的方式来保存数据。在这种方式下写操作是快了、高效了。那怎么来读呢？根据前面的介绍，数据是按照key-value来扁平化存储的。每条记录长度各不相同，既然要保证读，那就得额外保存一些信息来辅助处理用户的读请求。这些额外保存的数据，我们暂且称为索引。我们思索一下，在这种追加写的场景下，我们需要保存哪些信息才可以完成正常的读请求呢？其实每条记录我们只要知道了它写在磁盘的哪个位置(偏移量)offset、占了多长size这两个信息。我们就可以对其进行读了。简而言之，一条记录对应一个这样的二元组索引信息。简单示意图如下所以：到这儿，高效写可以了，维护了索引后，单个记录的读也可以了；但是有个问题我们得想想怎么办？那就是我们前面提到的排序、范围查找操作。在这种场景下，每来一条记录我们都是直接追加的，所以数据在磁盘上本身就是乱序存储的，既然需要排序、范围查找的话。那就得把磁盘上的所有记录都加载到内存中，然后再挨个挨个遍历判断，最后过滤出来满足条件的记录返回用户。这种方式能实现功能，但显然效率太低了。同时磁盘上存储的数据可能都远远超过内存大小了，所以这种方式根本就不可取。那有没有办法解决该问题呢？我们做一点假设：假设我们写磁盘的时候能保证顺序写的同时，写入的数据是有序的。比如，我们写入了三条数据，这三条数据本身写入的时候是排好序的，那么此时范围查找时，我们只要定位到第一条数据，后面的数据是有序的，就可以很快进行按序读取了。如果假设条件成立的话，那排序、范围查找这个问题就从根本上得到简化了。我们也就不用这么大费周折了。我们先基于这个简单假设来看一下，在假设条件成立的情况下，我们还需要解决哪些问题呢？在这种模式下，我们访问每条记录同时还是需要保留之前的结论：每条数据都维护一个索引项：offset、size。我们要存储的是千万级量级的数据，每一条记录都需要一个索引项，那么千万条的记录就需要维护千万条索引项。问题就接着产生了，这千万条的索引项怎么组织？选哪种数据结构组织?存哪里？...针对千万条索引项这个问题，我们来看看这个问题有没有解。直观的想法可能就分为两大类：能否减少索引项的个数？索引项个数减少，自然问题就好解决了不能减少索引项个数的情况下，是否可以找到合理的数据结构来组织。这儿的“合理”可以理解成：空间压缩、优化等等。我们先从按照第一个思路来看看吧！Q:为什么会产生千万条索引项呢？W:因为每一条记录都需要维护一个索引项，我们需要保存千万条记录，所以就得存储千万条索引项。Q:为什么每一条记录需要维护一个索引项呢？W:因为每一条记录都是从用户请求传递进来的，每条记录在按照行格式扁平化存储时，长度是不固定的，所以需要每一条记录维护一个索引项。到这儿我们知道了问题的核心原因了。到这儿我们将上面层层推导的内容用一张图来总结一下：3.4索引矛盾点索引核心矛盾点:根据前面的分析，每条记录是变长的，所以需要每条记录都维护一个索引项。变长、变长、变长，我们能从变长这个维度切入做一些改进或者优化吗？既然每条记录的长度我们无法控制，那是否可以将磁盘转化一下呢？我们如果将磁盘划分成一段一段的固定大小的连续块，对于每一块的话，我们记录一个块编号no来区分不同的块，假设我们的块大小是100个字节，那么第0块对应的范围是0~99，第1块对应的是100~199，依次类推。做了这样的改变后会发生什么呢？我们详细分析一下。将磁盘划分成一个一个的固定大小连续块后，每个块内仍然保留原先过程中的两大特性：数据有序并且顺序写。大致的结果如下图所以：这样改造以后，关键我们看看怎么保证读写呢？我们先假设我们的块空间足够大，这样的话就能避免出现一个块存不下一条记录的问题。正常情况下，我们的一个块会保存多条记录，并且块内的记录是有序存储的。我们在读取一条记录的时候，一条记录肯定是位于其中一块上，首先我们得解决这个定位问题。当定位到具体的块后，将当前块的数据从磁盘加载到内存中，块内部的数据是有序存储的，那自然就可以通过二分的方式来找到我们的具体数据对应的索引项了。最后再根据索引项来读取数据即可。同理写的过程虽然对外来看是对单条记录进行写，但内部是按照块作为单位来写磁盘。那问题就转化成了如何确定一条记录保存在哪一块上了？针对这个问题，我们就需要确定一块上具体存储的多条记录的具体范围。例如第0块保存的是id从0~10的记录；第1块保存的是id从11~23的记录。等等这样的话，当查询id为7的记录时，我们就很快可以知道该条记录存储在第0块上，然后再从第0块内部查找具体id为7的记录的索引项，最后再读取数据。怎么确定呢？自然就需要在原先只保存一个块编号no的基础上，再多保存两个信息：该块保存的记录最小值min、该块保存的记录的最大值max。每一块都对应这样一个三元组block->(no,min,max)。这个三元组表达的含义是：第no块保存的记录范围是min~max我们仔细再回想一下，其实这个三元组还是有改进空间的。因为我们写入的时候，每个块都是顺序写的并且块内数据是有序的，块间也是有序的。那也就是说：对于第i块而言，第i块存储的记录范围就是第i块的最小值拼接上第i+1块的最小值。其根本原因也就是存储的时候块间是有序的。那进一步我们就可以将上述三元组简化成一个二元组了block->(no,min)。同时附加保证每块之间保存的数据是逻辑有序的。前面啰里啰嗦说了一大堆，我们最后总结一下：引入了将磁盘划分成一个一个固定大小连续块的概念块内数据仍然按照有序、顺序写存储：块内仍然对每条记录保存两个信息：该记录写到磁盘的哪个位置offset、该条记录占多长size块间数据有序，每块需要保存两个信息：块编号no、该块保存的最小记录值min在引入这个块的概念后，我们看看当执行范围查找、排序等操作时，大部分情况下可以减少IO的次数，因为一次读取的一块数据，而一块中的数据包含多条记录。如果所涉及的数据在一块内的话，多条数据就只需要读取一次磁盘。所以在这种场景下，性能也会有所改善。整体大致的结构如下图所示：同时，我们还有两个遗留问题需要解决:1.块的大小定多大呢？2.块索引存不存？怎么存？针对第一个问题:块大小定多大？，我们可以辩证的来看。如果块大小越大，那么一块能保存的数据就越多，因此同等数据量级的条件下我们需要的块就越少，近而需要维护的块索引也就越少。但读写每条记录的时候额外读写的空间会越大(按照块读写)，因此读写效率越低。如果块大小越小，那么一块能保存的数据就越少，因此同等数据量级的条件下我们需要的块就越多，近而需要维护的块索引也就越多。但读写每条记录的时候额外读写的空间会越小(按照块读写)，因此读写效率越高。到这儿总算看出来了，其实块大小定多大就是一个折中问题。那我们怎么来选择呢？别忘了，我们的数据存储在磁盘，同时我们的应用时跑在操作系统上层，我们在这儿就想怎么让操作系统为我们的应用服务的更好呢？简而言之就是更好的利用操作系统的特性，让其发挥出最大的价值。我们每次读写数据都会涉及到磁盘操作，例如读写磁盘、刷盘等，而在数据写到磁盘前，数据会先写到内存中，在操作系统中管理内存时，有一个页的概念。操作系统读写磁盘、刷盘时机都和管理内存的页有不可分割的关系。因此那我们这块要不为了更好利用操作系统，就将操作系统页做为基本单位来确定块的大小，最简单也就是一块大小等于一页大小(默认4k)。更大也可以是8k、16k、32k等等。其实到这儿，我们也就回想起来了，innodb中默认的页大小就是16k；而在boltdb中，默认的页大小就是操作系统的页大小4k。既然选择的操作系统页作为块大小基本单位，那我们也不引入一个新的概念块了，我们也称块为页呗。减少大家对新名词的理解成本。第一个问题，到这儿我们也就解答完了。接下来我们看第二个问题。块索引存不存？怎么存？我们的答案是存，因为不存的话，当我们的应用重启时，就需要重新建块索引，当存储的数据量很大时，重建块索引是相当耗时的一件事情，在重建索引期间，可能会导致服务对外不可用。**所以我们需要存块索引。**那具体怎么存储呢？第一种：最简单划分独立的块来保存快索引该种方式在mysql中也被称为聚簇索引,索引和记录数据存储在一起，存储在一个文件中。第二种：将快索引采用单独的文件来保存该种方式在mysql中也被称为非聚簇索引,索引和记录数据分开存储，存储在不同的文件中。3.5b树还是b+树到此，我们的整体推导已经差不多接近尾声了，我们将上述推导做一个汇总，最终得到的结果如下图所示。上图中每个虚线框表示一页，其中每一页都保存数据(数据项或者索引项)，每一页之间也可以有指针指向确保页之间是逻辑有序的。其次每个页内部都包含多个数据项或者索引项，而且数据是有序存储的。如果我们把其中的黑线去掉后，剩余的这种结构是一种啥结构呢？答案是:多叉树，其中每页可以看做一个节点，该节点内部有多项，同时一个节点可以多有个孩子节点接下来我们再来回想个问题。现在我们可以基于这样的结构进行读写了。那我们来看看，当我们读取的时候，如果读取的数据正好是其中某一页保存的最小记录，那这时候如果我们的最小记录保存了数据的话，就可以直接返回了。而不用再往下遍历了。如果只保存一个最小记录关键字的话，那就还需要一直往下遍历。那我们就来看看每页中的索引项存或者不存该条记录的原始数据会有哪些差异点呢？根据上图的分析，我们可以看到，如果对应的页索引项中保存了原始数据，则它对应的就是b树的数据结构；如果不存储原始数据，则它对应的就是b+树的数据结构。分析清楚了存和不存的区别，那我们到底选择存还是不存呢？答案是:不存，因为同样大小的一页，如果页索引项存储了额外的原始数据的话，必然一页中存储的页索引个数就会减少。同时进一步会导致存储同等数据量级的情况下，存储时的树的高度会比不存时高太多。而树的高度在我们这个场景里其实对应的就是磁盘IO的次数。显然我们要快速、高效，那就要尽可能减少不必要的磁盘IO次数。所以不存。近而，我们也就确定了我们选择的数据结构就是b+树了。到此，我们就从最初的直观思路出发，找到了在磁盘上容易维护的数据结构：b+树。在我们的抽象和改进中，引入了页的概念，磁盘中按照页的单位来组织数据，页内部保存的数据有序存储，页间数据也是有序存储。同时在磁盘上的b+树中，非叶子节点保存页索引信息。其中包括(页编号no、该页保存的数据最小记录min)；叶子节点保存具体的记录数据。既然磁盘上选择了b+树存储，那自然内存中也就选择b+树实现咯。我们来看看二者之间如何相互转化。内存中b+树的节点对应磁盘上的一页。内存中一个节点内部的多项对应磁盘上每一页中保存每一个元素(每条记录数据or每个页索引项)。这儿再强调下：我们选择用b+树作为索引而不是b树作为索引的核心点在于，在存储同等数据量级的情况下，选择用b+树做索引时，要比用b树做索引。平均的磁盘IO次数要少。同时对b+树而言，不同请求的时间复杂度都比较平均。因为每条记录的数据都保存在叶子节点上。3.6总结到此我们尝试回答为什么选择b+树作为存储引擎索引结构这个问题就回答完毕了。我们用一张图来总结下：最后我们看一下数据结构的b+树长啥样，我们磁盘+内存中的b+树又长啥样。下图是数据结构中的b+树，此处我们就不再过多解释其b+树的特性了。下图是磁盘+内存中最后对应的b+树示意图。最后，我们在接下来的一节内容中尝试通过回答第三个问题来我们来佐证一下我们选择的这个方案。4.反向论证既然选择了用b+树来存储千万级数据量级的索引结构，那对于一个指定页大小的存储引擎，3层或者4层的b+树能存储多少条数据呢？通过这个问题，我们再来证明下，我们选择的方案是否能解决我们当初提到的存储千万级数据量级的数据这个问题。4.13层、4层b+树(innodb为例)各能存储多少数据?针对这个问题，我们如何做一个粗略的估算呢？我们都知道innodb中，默认的一页大小是16k，此处我们也就以16k来做近似的估算。在估算前，我们需要事先假设两个数据:假设非叶子节点中保存的页索引项，每一项的大小占16个字节。对于16k的一页而言，大约可以存储1000(16k/16)条索引项。假设叶子节点中保存的每条记录数据的平均大小为160个字节。对于16k的一页而言，大约可以存储100(16k/160)条记录。综上：对于3层的b+树而言，其所能存储的数据量级：1000*1000*100，大概10^8条对于4层的b+树而言，其所能存储的数据量级：1000*1000*1000*100，大概10^11条也就是说，一个3层的b+树，在此种场景下，大约可以存储的数据量级就在千万级。因此该解决方案是可以解决我们最初提出来的问题的。下图是一个简单的总结。4.2总结到此，我们也就回答完了三个问题。并通过回答这三个问题，探讨了面对读多写少场景时选择的b+树存储引擎背后的一些选型过程。值得说明的是本文纯属个人学习过程中的一点思考和琢磨。有理解或表达不正确之处还请各位指正。端午福利马上端午小长假了，给大家送10本鹅厂程序员写的新书：作者：王贝珊抽奖方式进入公众号后台回复：端午送书即可获取抽奖方式6月14日端午节19:00准时开奖