MySqL 的 B+树、 叶子节点、非叶子节点

文章目录叶子节点、非叶子节点一、非叶子节点只当“指路牌”不存真实数据是什么里面存什么作用只做导航二、叶子节点真正存数据的地方是什么里面存什么额外特点有序且双向相连三、用一张文字结构图直观感受四、为什么这么设计就能“IO少、速度快”解析 B 树、二叉查找树一、先纠正误区不是所有树都是“一个节点存一个值”二、一个节点里到底存了什么叶子节点、非叶子节点B 树本质就是一棵从上到下分层的树状目录结构一共就两类节点上面所有层 → 非叶子节点目录层最底下一层 → 叶子节点数据层一、非叶子节点只当“指路牌”不存真实数据是什么就是树的中间目录层最顶部的叫根节点中间的叫分支节点它们统一都叫非叶子节点。里面存什么只存两样东西索引键比如主键id的值10、20、30…下一层节点的地址相当于“页码”告诉你下一层的节点在磁盘的哪个位置它里面半条真实的行数据都没有比如你查id15的员工非叶子节点里不会存这个员工的姓名、年龄这些信息只会告诉你“15在第二个叶子节点里”。作用只做导航就像字典的拼音目录、部首目录它的唯一作用就是帮你快速定位到“数据在哪一页”本身不提供任何完整内容。比如你查 “张” 字先看声母目录找到 zh 对应的页码范围再翻到韵母目录找到 ang 对应的具体页码最后才翻到正文页前面两步的目录就全是非叶子节点只指路不存解释。二、叶子节点真正存数据的地方是什么是 B树最底下的一层也是 查询的最终目的地。里面存什么在 InnoDB 的聚簇索引里叶子节点存的是完整的一行数据id、name、age、phone、email … 所有字段的真实值这就是那句话的意思所有数据都存在叶子节点。你要的任何真实业务数据只能在最底层的叶子节点里找到上面的目录层里一概没有。额外特点有序且双向相连所有叶子节点按索引值从小到大排好序并且相邻的叶子节点之间用 “双向链表” 连起来。好处就是一旦你找到了起点比如 id100的第一条数据顺着链表往后挨个走就能把所有符合范围的数据都取出来天然支持范围查询和排序。三、用一张文字结构图直观感受B树是多叉树也叫多路搜索树不是二叉树。一个节点可以存很多个索引键不是只能存1个。例子里只画了2个id是为了画图方便做的极度简化实际一个节点里能存上千个id。【根节点非叶子】 id: 20 id: 50 / \ 【分支节点】 【分支节点】都是非叶子 id:10 id:15 id:30 id:40 / \ / \ 【叶子1】 ↔ 【叶子2】 ↔ 【叶子3】 ↔ 【叶子4】最底层存完整数据 id:1-9 id:10-19 id:20-29 id:30-49 存完整行 存完整行 存完整行 存完整行你查WHERE id 17的过程先到根节点17 20走左边分支到分支节点15 17 20走第二个叶子节点到叶子2节点找到id17的完整行数据查询结束上面两步走的都是非叶子节点纯指路最后一步到叶子节点才拿到真实数据。四、为什么这么设计就能“IO少、速度快”这就是之前说的 “矮胖结构” 的核心原因非叶子节点不存数据只存 键值 地址体积非常小。MySQL一页默认16KB一页就能存上千个主键值。一层就能覆盖上千个范围两层就能覆盖上百万条数据三层就能覆盖上亿条数据。所以百万级数据查询最多也就读3次磁盘根节点 → 分支节点 → 叶子节点速度极快。如果非叶子节点也存数据那一页存不了几个键树就会变得又高又瘦查一条数据要读十几次磁盘就慢了。解析 B 树、二叉查找树B树是多叉树也叫多路搜索树不是二叉树。一个节点可以存很多个索引键不是只能存1个。一、先纠正误区不是所有树都是“一个节点存一个值”你会有 “一个节点存一个id” 的印象大概率是之前见过二叉查找树二叉树每个节点只能存1个值最多分左右两个分叉。B树每个节点可以存N个值分出N1个分叉所以叫“多叉树”。这也是B树能做到“矮胖”、IO次数少的根本原因。二、一个节点里到底存了什么我们拿非叶子节点举例它的内部结构是「索引键」和「子节点指针」交替排列。规则很简单如果一个节点里有N 个索引键就会对应N1 个子节点指针。每个指针负责指向一个数值区间。就拿你图里的根节点举例根节点里的值id: 20 id: 50 对应指针 ↙ ↓ ↘ 指针1 指针2 指针3三个指针对应三个区间指针1所有id 20的数据去左边的子节点找指针2所有20 ≤ id 50的数据去中间的子节点找指针3所有id ≥ 50的数据去右边的子节点找上面那个图里只画了两个分支是因为画图时把最右边大于50的部分省略了属于简化示意。为什么要这么设计一页目录能放下几十个分界标记就能指引几十页正文目录本身就不用做太厚。对应到数据库一个节点就是MySQL的一页数据默认16KB只存索引键指针能放下上千个id。一层就能划分上千个区间两层就能覆盖上百万条数据三层就能覆盖上亿条。树的高度只有3-4层查一条数据最多读3次磁盘这就是B树快的核心。如果一个节点只能存1个id二叉树那百万条数据树高就有20层查一次要读20次磁盘速度会慢很多。