【.com原稿】前几天，下班回家后，正在处理一个白天还没解决的bug，厕所里突然传来主题的声音……主题：xx，你有《时间简史》吗？我：我去！姐，你有什么爱好，我有空就不去捡屎了！主题：……人家说是史蒂芬霍金的科普书《时间简史》，是一本书！我：哦，那我没有……对象：我想看，你明天帮我去图书馆借一本……我：我明天得换……对象：你呢不爱我了，分手！I:我一大早就去了~第二天一早就到了图书馆。一进门就看到了标有不同楼层功能的索引牌，方便我快速定位到我要找的目标楼层。上楼的时候看到每一排书架都细分了书籍的分类，这样可以更快的定位到我要找的书的具体书架！并且每层楼都有一个查询终端，输入书名就可以找到对应的唯一标识“索书号”，类似于P159-49/164这样的一个代码，书架上的书都是按照这个代码排序的！有了这个代码，去对应的书架上，就可以快速的找到对应的书在书架上的具体位置。不到十分钟，我就从图书馆借了一本书出来了。这么大的图书馆，为什么我能在这么短的时间内找到我想要的书呢？如果这些书乱七八糟地堆放着，或者毫无征兆地放在书架上，我还能这么快找到吗？这让我怀疑我想到了我们开发中使用的数据库。图书馆的图书类似于我们数据表中的数据，楼层索引标志、书架分类标记、索书号类似于我们查找数据的索引。我们常用的数据库索引的底层数据结构是什么？想到这里，我又回到图书馆借了一本书?！要了解数据库索引的底层原理，首先要了解一种叫做树的数据结构，而树中一个非常经典的数据结构就是二叉树！那么下面我们就从二叉树到平衡二叉树，再到B-树，最后到B+树，一步步了解数据库索引的底层原理！二叉树（BinarySearchTrees）二叉树是一种树结构，其中每个节点至多有两个子树。通常子树被称为“左子树”和“右子树”。二叉树通常用于实现二叉搜索树和二叉堆。二叉树具有以下性质：每个节点包含一个元素和n个子树，其中0≤n≤2。左子树和右子树是有序的，不能随意颠倒顺序。左子树的值小于父节点，右子树的值大于父节点。光看概念有点无聊。假设我们现在有这样一组数字[35274812293855]，将它们依次插入到一个数字结构中。步骤如下：嗯，这是一棵二叉树！我们可以看到经过一系列的插入操作，原来无序的数集变成了有序的结构，这棵树满足了上面提到的两种二叉树的特点！但是如果Number上面的同一组数，我们按升序排列再插入，也就是说按照[12272935384855]的顺序插入，会出现什么情况呢？因为是升序插入，所以新插入的数据总是比已有节点的数据都大，所以每次都会往节点右边插入，最终会导致树严重偏向！上图是最坏的情况，就是一棵树退化成一个线性链表，那么搜索效率自然就低了，树的优势没有被充分发挥出来！为了使二叉树的搜索效率最大化，二叉树不再有偏向，保持各个分支的平衡，所以就有了平衡二叉树！平衡二叉树（AVLTrees）平衡二叉树是一种特殊的二叉树，所以它也满足了上面提到的二叉树的两个特性，而且还有一个特性：它的左右子树的高度差的绝对值不不超过1，左右子树都是平衡二叉树。插入完成后你也看到了之前的[35274812293855]图。其实已经是平衡二叉树了。那么如果按照[12272935384855]的顺序插入一棵平衡二叉树会怎样呢？我们看一下插入和平衡的过程：这棵树总是满足平衡二叉树的几个特点，保持平衡！这样我们的树就不会退化成线性链表了！当我们需要找一个数的时候，我们可以沿着树的根向下走。查找效率和二分查找一样！一棵平衡二叉树能容纳多少？节点呢？这与树的高度有关。假设树的高度为h，则每一层最多可容纳的节点数为2^(n-1)，整棵树最多可容纳的节点数为2^0+2^1+2^2+...+2^(h-1)。这样算下来，100w的数据树的高度约为20，也就是说，要从一棵有100w条数据的平衡二叉树中找到一条数据，最坏情况下需要查找20次。如果是内存操作，效率也是很高的！但是我们数据库中的数据基本都是放在磁盘上的。每次读取二叉树的一个节点就是一次磁盘IO，那么如果我们找一条数据，如果要经过磁盘20次IO呢？那么性能就成了大问题！那我们是不是可以压缩这棵树，让每一层可以容纳更多的节点呢？我虽然矮，但是我胖。。。B-Tree是一棵又矮又胖的树就是B-Tree。注意中间是bar而不是minus，所以不要读成BminusTree~B-Tree有什么特点呢？一棵m阶的B树-Tree有如下特点：每个节点至多有m个子节点。除了根节点和叶节点之外，每个节点至少有m/2（向上取整）个子节点。如果根节点不是叶节点，则根节点至少包含两个子节点。所有叶节点都位于同一层。每个节点包含k个元素（关键字），其中m/2≤k。每个节点中的元素（关键字）从小到大排列。每个元素（关键字）的左节点的值小于或等于该元素（关键字）。右边节点的值都大于等于元素（关键字）。有没有一种婆婆向你要彩礼的感觉，罗列了一堆条件，每一个都让你很迷茫！我们以一个[0,1,2,3,4,5,6,7]为例，把一个数组插入3级B-Tree，把所有条件串起来，你就明白了！那么，你对B-Tree的特性了解清楚了吗？在二叉树中，每个节点Point只有一个元素。但是在B-Tree中，每个节点可能包含多个元素，非叶子节点有指向元素左右子节点的指针。如果我们需要找到一个元素，这个过程是怎样的？我们看下图。如果我们要在下面的B-Tree中查找关键字24，过程如下：从这个过程中我们可以看出B-Tree的查询效率似乎并不比平衡二叉树高。但是查询传递的节点数少了很多，也就意味着磁盘IO少了很多，大大提高了性能。从前面的B-Tree操作图可以看出，元素都是1、2、3这样的值。但是数据库中的数据是一条数据。如果数据库将数据存储在B-Tree数据结构中，那么数据是如何存储的？我们看下一张图：在一个普通的B-Tree的节点中，element只是数字。但是在上图中，我们将元素部分拆分成了key-data的形式，Key是数据的主键，Data是具体的数据。这样我们在找数的时候，往根节点往下找就可以了，效率比较高。B+TreeB+Tree是在B-Tree的基础上进行优化，使其更适合实现外部存储的索引结构。B+Tree的结构与B-Tree非常相似，但也有自己的几个特点：所有非叶子节点只存储关键字信息。所有卫星数据（特定数据）都存储在叶节点中。所有叶节点都包含有关所有元素的信息。所有叶节点之间都有一个链接指针。如果上面的B-Tree图变成B+Tree，应该是这样的：仔细比较一下，你能发现和B-Tree图有什么不同？非叶子节点上只有Key信息，满足上面第一个特征！所有的叶子节点下面都有一个Data区，满足了上面的第二个特征！非叶子节点的数据可以在叶子节点上找到，比如根节点的元素4和8也可以在底部叶子节点上找到。可以找到，满足上面第三个特征！注意图中叶子节点之间的箭头，满足上面第四个特征！B树还是B+树？在讲数据库中这两种数据结构的选择之前，我们需要了解的另一个知识点是，操作系统是根据磁盘块（Block）将数据从磁盘读取到内存中的。同一磁盘块中的数据会被一次性读出，而不是需要什么就取什么。即使只需要一个字节，磁盘也会从这个位置开始，依次向后读取一定长度的数据到内存中。其理论依据是计算机科学中众所周知的局部性原则：当使用一条数据时，通常会立即使用附近的数据。预读的长度一般是页（Page）的整数倍。页是计算机管理的内存的逻辑块。硬件和操作系统通常将主内存和磁盘存储区域划分为大小相等的连续块。每个存储块称为一个页面（在许多操作系统中，一个页面的大小通常为4K）。B-Tree和B+Tree如何选择？有什么优点和缺点？①B-Tree在非叶子节点中也存储了特定的数据，因此在搜索关键字时，可以找到并返回。但是B+Tree的所有数据都在叶子节点中，每次查找都会得到叶子节点。因此，在相同高度的B-Tree和B+Tree中，B-Tree在查找某个关键字时效率更高。②由于B+Tree的所有数据都在叶子节点中，节点之间有指针连接，所以在查找大于或小于某个关键字的数据时，B+Tree只需要找到关键字然后沿着链表，而B-Tree也需要遍历关键字节点的根节点进行查找。③因为B-Tree的每个节点（这里的节点可以理解为一个数据页）存储的是主键+实际数据，而B+Tree的非叶子节点只存储关键字信息，每页的大小是有限的,所以同一个页面在B-Tree中可以存储的数据比在B+Tree中少。这样，对于同样数量的数据，B-Tree的深度会更大，这会增加查询时的磁盘I/O次数，从而影响查询效率。综上所述，在常用的关系型数据库中，都是选择B+Tree的数据结构来存储数据！下面以MySQL的InnoDB存储引擎为例进行讲解，其他原理与SQLServer和Oracle类似！InnoDBengine数据存储在InnoDB存储引擎中，同样有页的概念。每页默认大小为16K，即每次读取数据时读取4*4K的大小！假设我们现在有一个user表，我们去往里面写数据：这里需要注意的一点是，在一个page中插入新行的时候，为了减少数据的移动，一般都是插入到当前行之后或者剩余的空间中由于被删除的行，所以在一个页面里面的数据并不是完全有序的（后面会详细介绍页面的结构）。但是为了数据访问的顺序性，每条记录中都有一个指向下一条记录的指针，这样就形成了一个单向有序链表，不过这里我为了演示方便，是按顺序排列的！由于数据还是比较少，一页可以容纳，所以只有一个根节点，主键和数据也存储在根节点中（左边的数字代表主键，名字和性别右边代表具体数据）。假设我们写了10条数据，Page1写满了，新的数据怎么存？我们继续看下图：一个叫“秦守生”的朋友来了，但是Page1已经装不下数据了。这时候就需要进行页面拆分，生成新的Page。InnoDB中的进程是什么？生成一个新的Page2，然后将Page1的内容复制到Page2中。生成新的Page3，将“秦守生”的数据放入Page3。原来的Page1仍然作为根节点，但是变成了一个不存储数据只存储索引的页面，并且有两个子节点Page2和Page3。这里有两个需要注意的问题：①为什么要将Page1复制到Page2而不是新建一个页面作为根节点，这样可以减少一步复制的开销？如果重新创建根节点，则根节点点存储的物理地址可能会经常变化，不利于查找。而且在InnoDB中，根节点会被预读到内存中，所以最好固定节点的物理地址！②本来Page1有10条数据，当插入第11条数据时，进行裂变。根据前面分析B-Tree，B+Tree的特性，那么这至少是一个11阶的树，裂变后每个节点的元素至少是11/2=5。页面裂变后主键1-5的数据是不是应该留在原来的页面，主键6-11的数据会放到新的页面，根节点会存放主键6？如果是这样的话，新的页面空间利用率只有50%，并且会造成更频繁的页面拆分。所以InnoDB对此进行了优化，新数据放入新创建的页面中，原页面的任何记录都没有移动。随着数据的不断写入，这棵树逐渐茂盛，如下图所示：每增加新的数据，就填充一个页面，然后创建一个新的页面继续写入。其实还有一个隐含的Conditional，那就是主键自增！主键自增时，新插入的数据不会影响原来的页面，插入效率高！而且页面的使用率很高！但是如果主键是乱序的或者是随机的，那么每次插入都可能会导致原页面的频繁分裂，影响插入效率！降低页面利用率！这就是为什么建议在InnoDB中设置主键自增的原因！这棵树的所有非叶子节点存储的都是主键，那么如果一张表没有主键会怎样呢？在InnoDB中，如果一张表没有主键，默认会找一个有唯一索引的列。如果没有，则会生成一个不可见的字段作为主键！有数据插入和删除，如果用户表频繁插入和删除，会造成数据页碎片化，页空间利用率低，还会导致树“虚高”，减少查询效率！这个可以通过索引Rebuild来消除碎片，提高查询效率！InnoDB引擎数据搜索如何找到插入的数据？找到数据所在的页面。这个查找过程和上面说的B+Tree查找过程是一样的，都是从根节点开始到叶子节点。在页面上查找特定数据。将步骤1找到的叶子节点数据读入内存，然后通过分块查找找到具体数据。这和我们在新华字典里找某个汉字是一样的。首先通过字典的索引定位到该汉字的拼音所在的页面，然后在指定的页面上找到具体的汉字。在InnoDB中定位页面后，采用哪种策略快速找到主键？我们需要从页面结构开始。左侧的蓝色区域称为页面目录。该区域由多个Slot组成。是一种稀疏索引结构，即一个slot可能属于多条记录，最少4条记录，最多8条记录。槽中的数据是有序存储的，所以我们在查找一条数据时，可以先通过二分法在槽中找到一个大概的位置。右边的区域是数据区，每个数据页包含多行数据。注意图中上下两条特殊的线记录Infimum和Supremum，这是两条虚线记录。在没有其他用户数据的情况下，Infimum的下一条记录指针指向Supreme。有用户数据时，Infimum的下一条记录指针指向当前页最小的用户记录，当前页最大用户记录的下一条记录指针指向Supreme，至此所有行记录在整个页面中形成一个单一的链表。行记录在逻辑上被PageDirectory分成多个块，块是有序的。也就是说，“4”槽指向的数据块中最大行记录的主键高于“8”槽的主键。指向的数据块中最小行记录的主键较小。但是块内的行记录不一定是有序的。每条记录都有一个n_owned区域（图中粉色区域），n_owned标识了这个块有多少条数据。伪记录Infimum的n_owned值始终为1，记录Supreme的n_owned取值范围为[1,8]，其他用户记录的n_owned取值范围为[4,8]。而每个块中只有最大记录的n_owned才会有值，其他用户记录的n_owned都会为0。所以当我们要查找主键为6的记录时，首先要在稀疏中找到对应的槽通过二分法索引，即页面目录中的槽“8”。槽“8”指向数据块中最大的记录，数据是单向链表结构，不能反转。所以需要找到上一个槽位，也就是槽位“4”，然后通过槽位“4”中最大用户记录的指针，沿着链表依次查找目标记录。Clusteredindex&non-clusteredindex前面的数据存储是通过聚集索引实现演示的。如果上面的用户表需要创建一个带有“用户名”的非聚集索引，它是如何实现的呢？我们看下图：非聚簇索引的存储结构和之前一样，不同的是叶子节点的数据部分不再存储具体的数据，而是聚簇索引的Key数据。因此，通过非聚簇索引查找的过程就是先找到该索引Key对应的聚簇索引的Key，然后将聚簇索引的Key拿到主键索引树中查找对应的数据。这个过程叫做回表！PS：图中这些名称均来自网络，希??望不要误伤正在阅读本文的你~^_^InnoDB和MyISAM引擎对比以上包括存储和搜索使用InnoDB引擎为例，所以MyISAM和InnoDB在存储方面有什么区别？憋不住的话，看图：上图是MyISAM主键索引的存储结构。我们可以看出不同的是，主键索引树的叶子节点的数据区并没有存储实际的数据，而是存储了数据记录的地址。数据的存储不是按照主键的顺序存储的，而是按照写入的顺序存储的。也就是说，InnoDB引擎数据在物理上是按照主键顺序存储的，而MyISAM引擎数据在物理上是按照插入顺序存储的。而MyISAM的叶子节点不存储数据，所以非聚集索引的存储结构与聚集索引类似。使用非聚集索引查找数据时，可以直接通过非聚集索引树找到数据的地址，无需返回表。这比InnoDB的查找效率还高！索引优化建议在很多文章或书籍中经常可以看到一些索引的使用建议，例如：like的模糊查询以%开头，会导致索引失效。尽量不要为一个表创建超过5个索引。尽可能使用覆盖索引。尽量不要在有大量重复数据的列上建立索引。……很多就不一一列举了！那么看完这篇文章，我们是不是可以分析一下，为什么我们会有这些建议，心存疑惑呢？为什么like的模糊查询以%开头，会导致索引失败？为什么一张表建的索引不要超过5个？为什么？有大型互联网项目开发经验，对高并发、分布式、微服务技术有深入研究和相关实践经验。经验丰富的自学，热衷于技术研究和分享！座右铭：永远保持虚心的学习态度！【原创稿件，合作网站转载请注明原作者及出处为.com】
