草庐IT

MySQL索引底层为什么用B+树？看完这篇文章，轻松应对面试。

一灯架构 2023-03-28 原文

迎面走来了你的面试官，身穿格子衫，挺着啤酒肚，发际线严重后移的中年男子。
手拿泡着枸杞的保温杯，胳膊夹着MacBook，MacBook上还贴着公司标语：“我爱加班”。

面试开始，直入正题。

面试官： 你知道MySQL索引底层数据结构为啥用B+树？而不用B树、红黑树或者普通二叉树？

我： 这事谁知道作者咋想的？他可能是用B+树习惯了，个人爱好吧。

面试官： 你倒是挺看得开。今天的面试就先到这吧，后面有消息会主动联系你。

后面还可能有消息吗？你们啥时候主动联系过我？
实话实说的被拒，八股文背得溜反而被录取。
好吧，等我看看一灯怎么总结的MySQL的八股文。

我： 要知道MySQL索引底层数据结构为啥用B+树，先要了解一下什么样的数据结构更适合建索引。

为了保证数据安全性，一般都是把数据存储在磁盘里面。当我们需要查询数据的时候，需要读取磁盘，就产生了磁盘IO，相比较内存操作，磁盘IO读取速度是非常慢的。

由于所需数据可能在磁盘并不是连续的，一次数据查询就需要多次磁盘IO，所以就需要我们设计的索引数据结构尽可能的减少磁盘IO次数。

再了解一下这几种二叉树的特性，以及优缺点，就知道哪种数据结构更适合建索引。

什么是二叉搜索树：

  1. 若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
  2. 若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
  3. 左、右子树也分别为二叉查找树；

二叉搜索树查找数据的时间复杂度是O(logN)，如图所示，最多查找3次就可以查到所需数据。

理想很丰满，现实很骨感。极端情况下，二叉查找树可能退化成线性链表。

链表的查找时间复杂度是O(N)，这时候最多需要7次才能查到所需数据。

该怎么办呢？于是我们就想到了给二叉树加一些限制条件，平衡一下左右子树，然后就引申出了很多平衡树：平衡二叉查找树、红黑树、B树、B+树。咱们分别说一下这几种树的优缺点，看哪种树最适合做索引。

什么是红黑树？

  1. 结点是红色或黑色
  2. 根结点是黑色
  3. 所有叶子都是黑色（叶子是NIL结点）
  4. 每个红色结点的两个子结点都是黑色（从每个叶子到根的所有路径上不能有两个连续的红色结点）
  5. 从任一结点到其每个叶子的所有路径都包含相同数目的黑色结点

看蒙了没有？

这么多复杂的规则，就是为了保证从根节点到叶子节点的最长路径不超过最短路径的2倍。

当插入节点或者删除节点的时候，为了满足红黑树规则，可能需要变色和旋转，这是一个复杂且耗时的过程。

红黑树的优点：
限制了左右子树的树高，不会相差过大。

缺点：
规则复杂，一般人想要弄懂这玩意儿，就已经很费劲了，更别说使用了。

什么是B树？

我们知道，树的高度越高，查找次数越多，也就是磁盘IO次数越多，耗时越长，
我们能不能想办法降低树的高度，把二叉树变成N叉树？于是B树就来了。

对于一个m阶的B树：

  1. 根节点至少有2个子节点
  2. 每个中间节点都包含k-1个元素和k个子节点，其中 m/2 <= k <= m
  3. 每个叶子节点都包含k-1个元素，其中 m/2 <= k <= m
  4. 中间节点的元素按照升序排列
  5. 所有的叶子结点都位于同一层

根节点（8）有两个子节点，左子节点（3 5）和右子节点（11 15）。
左子节点（3 5）中有2个元素和3个子节点。
元素是3和5，按照升序排列。
子节点是（1 2）、（4）、（6 7），
而（1 2）中元素小于3，（4）中的元素在3和5中间，（6 7）的元素大于5，符合B树特征。

B树这样的设计有哪些优点呢？

高度更低，每个节点含有多个元素，查找的时候一次可以把一个节点中的所有元素加载到内存中作比较，两种改进都大大减少了磁盘IO次数。

什么是B+树？

相比较B树，B+树又做了如下约定：

  1. 有k个子节点的中间节点就有k个元素（B树中是k-1个元素），也就是子节点数量 = 元素数量。
    每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。

  2. 所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

  3. 非叶子节点只保存索引，不保存数据。（B树中两者都保存）

  4. 叶子结点包含了全部元素的信息，并且叶子结点按照元素大小组成有序列表。

B+树这样设计有什么优点呢？

  1. 每个节点存储的元素更多，看起来比B树更矮胖，导致磁盘IO次数更少。
  2. 非叶子节点不存储数据，只存储索引，叶子节点存储全部数据。
    这样设计导致每次查找都会查到叶子节点，效率更稳定，便于做性能优化。
  3. 叶子节点之间使用有序链表连接。
    这样设计方便范围查找，只需要遍历链表中相邻元素即可，不再需要二次遍历二叉树。

很明显，B树和B+树就是为了文件检索系统设计的，更适合做索引结构。

面试官： 还得是你，就你总结的全，我都想不那么全，明天来上班吧，薪资double。

本文知识点总结：

文章持续更新，可以微信搜一搜「 一灯架构 」第一时间阅读更多技术干货。

底层篇文章strongli734446Java

有关MySQL索引底层为什么用B+树？看完这篇文章，轻松应对面试。的更多相关文章

  1. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  2. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  3. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  4. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  5. ruby - 为什么 4.1%2 使用 Ruby 返回 0.0999999999999996？但是 4.2%2==0.2 - 2

    为什么4.1%2返回0.0999999999999996？但是4.2%2==0.2。 最佳答案 参见此处:WhatEveryProgrammerShouldKnowAboutFloating-PointArithmetic实数是无限的。计算机使用的位数有限(今天是32位、64位)。因此计算机进行的浮点运算不能代表所有的实数。0.1是这些数字之一。请注意，这不是与Ruby相关的问题，而是与所有编程语言相关的问题，因为它来自计算机表示实数的方式。 关于ruby-为什么4.1%2使用Ruby返

  6. ruby - ruby 中的 TOPLEVEL_BINDING 是什么？ - 2

    它不等于主线程的binding，这个toplevel作用域是什么？此作用域与主线程中的binding有何不同？>ruby-e'putsTOPLEVEL_BINDING===binding'false 最佳答案 事实是，TOPLEVEL_BINDING始终引用Binding的预定义全局实例，而Kernel#binding创建的新实例>Binding每次封装当前执行上下文。在顶层，它们都包含相同的绑定(bind)，但它们不是同一个对象，您无法使用==或===测试它们的绑定(bind)相等性。putsTOPLEVEL_BINDINGput

  7. ruby - Infinity 和 NaN 的类型是什么？ - 2

    我可以得到Infinity和NaNn=9.0/0#=>Infinityn.class#=>Floatm=0/0.0#=>NaNm.class#=>Float但是当我想直接访问Infinity或NaN时:Infinity#=>uninitializedconstantInfinity(NameError)NaN#=>uninitializedconstantNaN(NameError)什么是Infinity和NaN？它们是对象、关键字还是其他东西？ 最佳答案 您看到打印为Infinity和NaN的只是Float类的两个特殊实例的字符串

  8. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  9. ruby - 为什么 SecureRandom.uuid 创建一个唯一的字符串？ - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion为什么SecureRandom.uuid创建一个唯一的字符串？SecureRandom.uuid#=>"35cb4e30-54e1-49f9-b5ce-4134799eb2c0"SecureRandom.uuid方法创建的字符串从不重复？

  10. ruby - 当使用::指定模块时，为什么 Ruby 不在更高范围内查找类？ - 2

    我刚刚被困在这个问题上一段时间了。以这个基地为例:moduleTopclassTestendmoduleFooendend稍后，我可以通过这样做在Foo中定义扩展Test的类:moduleTopmoduleFooclassSomeTest但是，如果我尝试通过使用::指定模块来最小化缩进:moduleTop::FooclassFailure这失败了:NameError:uninitializedconstantTop::Foo::Test这是一个错误，还是仅仅是Ruby解析变量名的方式的逻辑结果？ 最佳答案 Isthisabug,or

随机推荐