面试官：谈谈你对索引系列B-tree的理解

本文转载自微信公众号《架构改进之路》，作者的架构改进之路。转载本文请联系建筑改良之路公众号。至于MySQL索引，相信每个后端同学在日常工作中都会经常用到，但未必对索引原理有真正深入的了解。结果，在面试过程中，如果他们不能回答关键点，他们可能不得不处理机会。说再见。面试官：MySQL的索引实现是用什么数据结构的？你：好像是B+树。面试官：为什么用B+树而不是B-树？你：...面试官：用B+树来实现索引结构，有什么好处？你：...B-tree和B+树是MySQL索引使用的数据结构，对于索引优化和原理理解非常重要。下面就为大家揭开B-tree和B+树的神秘面纱，让大家多多学习。当你在面试的时候遇到这个知识点，你就会勇往直前，不再是你前进的羁绊！B-tree简介B-tree，其中B的意思是balance（平衡的意思），B-tree是一种多路平衡搜索树，它类似于普通的平衡二叉树，不同的是B-trees允许每个节点有更多的子节点。从上面B树的简化图，我们可以发现几个显着的特点：所有的键值都分布在整棵树中（索引值和具体数据在每个节点中），叶子节点的深度相同;any关键字出现且只出现在一个节点中；搜索可能会在非叶节点处结束（在最好的情况下O(1)可以找到数据）；在关键字全集上做一次搜索，性能接近二分搜索平衡二叉树VSB-tree我们知道传统上用于搜索的平衡二叉树有很多，比如AVL树，红黑树等等在。这些树对于一般的查询性能非常好，但是当数据非常大的时候就无能为力了。原因是当数据量很大时，内存不够用，大部分数据只能存放在磁盘上，只有需要的数据才会加载到内存中。一般来说，内存访问时间约为50ns，而磁盘约为10ms。速度相差近5个数量级，磁盘读取时间远远超过内存中数据比较的时间。这意味着该程序将在大多数时间阻塞磁盘IO。那么我们如何提高程序性能呢？平衡二叉树平衡二叉树是靠旋转来维护的，旋转是对整棵树的操作。如果其中一部分加载到内存中，旋转操作将无法完成。其次，平衡二叉树的高度比较大，有logn（基数为2），所以逻辑上很近的节点实际上可能相距很远，不能很好地利用磁盘预读（局部性原则）。空间局部性原则：如果内存中的某个位置被访问，那么它附近的位置也会被访问。B-treeB-treemulti-fork的好处非常明显，有效的降低了B-tree的高度（logn，基数很大，基数的大小与该节点的子节点个数有关，一般B树的高度在3层左右）。层数越低，每个节点区域确定的范围越准确，范围缩小的越快（肯定比二叉树的深度搜索快很多）。上面说到一个节点需要执行一次IO，所以总的IO次数减少到logn次。B-tree的每个节点都是n个有序序列(a1,a2,a3...an)，将该节点的子节点分成n+1个区间进行索引(X1an)。B树搜索让我们看一下B树搜索。假设每个节点有n个键值，分为n+1个区间。注意，每个键值后面都是数据域，也就是说B-树的键和数据是聚合在一起的。一般来说，根节点在内存中，B-tree将每个节点作为磁盘IO。如果查找key为25个节点的数据，先对根节点进行二分查找（因为key是有序的，二分查找最快），判断key25小于key50，所以定位到最左边的节点，此时进行一次磁盘IO。将节点从磁盘读入内存，然后继续上述过程，直到找到key。总结索引的效率取决于磁盘IO的数量，快速索引需要有效减少磁盘IO的数量。Q：如何实现快速索引？索引的原理其实就是不断缩小搜索范围，就像我们平时查字典一样，先找第一个字母缩小范围，再找第二个字母，以此类推。平衡二叉树每次将范围划分为两个区间；B树每次将范围划分为多个区间。间隔越多，定位数据越快、越准确。然后，如果节点是区间范围，则每个节点将更大。因此，在新建节点时，直接申请page-sized的空间（磁盘存储单元以block为单位划分，一般为512Byte。磁盘IO一次读取几个block，我们称之为page。具体大小与操作系统，一般为4k、8k或16k)，计算机内存分配是页对齐的，这样一个节点只需要一个IO。为什么会存在像B树这样的结构？任何事物的存在都是有原因的。B-tree的设计是比较平衡的二叉树，看起来更“迎合”磁盘的角度。