登录
首页 >  数据库 >  MySQL

B+树的正确姿势

来源：SegmentFault

时间：2023-02-24 12:16:58 467浏览 收藏

本篇文章向大家介绍《B+树的正确姿势》，主要包括MySQL、数据结构、InnoDB，具有一定的参考价值，需要的朋友可以参考一下。

背景

用过

1
MySQL
的同学都知道高效查询需要走索引，否则全表读取会导致慢SQL。
1
InnoDB
的索引是采用
1
B+树
实现的。网络和书本上关于
1
B+树
的定义各不相同，读者们可能都分辨不清哪个是准确的定义。

定义

笔者按照《数据库系统概念》（Database System Concepts）这本书上的概念，准确定义

1
B+树
。

1
B+树
采用的是平衡树结构，从根节点到每个叶子节点的路劲长度都是相同的，我们给每棵树定义
1
n
，
1
n
是固定不变的，下图是
1
B+树
节点全满状态的结构：

alt text

P表示指针，K表示关键字，且如果
1
2
3
i ,则<pre class="brush:go;">K<sub>i</sub>j</pre>(假设没有重复的关键字)。
<p>对于叶节点，</p><pre class="brush:go;">i = 1,2,···,n-1</pre>, 指针<pre class="brush:go;">P<sub>i</sub></pre>指向具有关键字<pre class="brush:go;">K<sub>i</sub></pre>的一条文件记录，指针<pre class="brush:go;">P<sub>n</sub></pre>指向后一个叶节点，这样所有的叶节点按键值大小顺序串成一个链表，可以高效地进行顺序处理。
<p>非叶节点的结构与叶节点相同，只不过非叶节点的指针都是指向树中的节点。假设有</p><pre class="brush:go;">K<sub>i-1</sub>,P<sub>i</sub>,K<sub>i</sub></pre>，则指针<pre class="brush:go;">P<sub>i</sub></pre>指向的子树中的关键字值大于等于<pre class="brush:go;">K<sub>i-1</sub></pre>，小于<pre class="brush:go;">K<sub>i</sub></pre>；<pre class="brush:go;">P<sub>1</sub></pre>指向的子树的关键字值，小于<pre class="brush:go;">K<sub>1</sub></pre>；<pre class="brush:go;">P<sub>n</sub></pre>指向的子树的关键字值都大于等于<pre class="brush:go;">K<sub>n-1</sub></pre>。

  • 对任意节点，指针数 = 关键字数 + 1

  • 对于任意非叶节点，其指针数必须满足

    1
    [ceil(n/2), n]

  • 若非叶节点是根节点，则其指针数可以小于

    1
    ceil(n/2)
    ，但至少包含两个指针，除非整棵树只有一个节点

  • 对于任意叶节点，其关键字数必须满足

    1
    [ceil((n-1)/2), n-1]

  • 若叶节点是根节点，则其关键字数可以小于

    1
    ceil((n-1)/2)

更新

关于

1
 
树的查找、插入、删除操作，请参考本人
1
github
：

https://github.com/butterflyl...

原文链接

https://segmentfault.com/a/11...

今天关于《B+树的正确姿势》的内容就介绍到这里了，是不是学起来一目了然！想要了解更多关于mysql的内容请关注golang学习网公众号！

mysql MySQL 数据结构 InnoDB
声明：本文转载于：SegmentFault 如有侵犯，请联系study_golang@163.com删除
相关阅读
更多>
最新阅读
更多>
课程推荐
更多>
评论列表