看图轻松理解数据结构与算法系列(B树)
前言
推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。
B树
B树即平衡查找树,一般理解为平衡多路查找树,也称为B-树、B_树。是一种自平衡树状数据结构,能对存储的数据进行O(log n)的时间复杂度进行查找、插入和删除。B树一般较多用在存储系统上,比如数据库或文件系统。
B树特点
- B树可以定义一个m值作为预定范围,即m路(阶)B树。
- 每个节点最多有m个孩子。
- 每个节点至少有ceil(m/2)个孩子,除了根节点和叶子节点外。
- 对于根节点,子树个数范围为[2,m],节点内值的个数范围为[1,m-1]。
- 对于非根节点,节点内的值个数范围为[ceil(m/2)-1,m-1]。
- 根节点(非叶子节点)至少有两个孩子。
- 一个有k个孩子的非叶子节点包含k-1个值。
- 所有叶子节点在同一层。
- 节点内的值按照从小到大排列。
- 父节点的若干值作为分离值分成多个子树,左子树小于对应分离值,对应分离值小于右子树。
以下是一个四阶B树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/3e5571df7b3f483ba729b84d63069906.webp)
插入
假设现在构建一棵四阶B树,开始插入“A”,直接作为根节点,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/9da12186a5ec4ebcb6ed31184565d79f.webp)
插入“B”,大于“A”,放右边,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/5357d2e435144819a550908fe40049fb.webp)
插入“C”,按顺序排到最后,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/6729f26f08ca43e3a360a3363fc3f670.webp)
继续插入“D”,直接添加的结果如下图,此时超过了节点可以存放容量,对于四阶B树每个节点最多存放3个值,此时需要执行分裂操作,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/16b3e14102ed4cacbf44f086c8fee601.webp)
分裂操作为,先选取待分裂节点的中值,这里为“B”,然后将中值“B”放到父节点中,因为这里还没有父节点,那么直接创建一个新的父节点存放“B”,而原来小于“B”的那些值作为左子树,原来大于“B”的那些值作为右子树。
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/01ab211f30b342f19db9f5410d651acd.webp)
继续插入“E”,"E"大于“B”,往右子节点,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/5816215faaeb43acaed0f50175ca01de.webp)
分别于“C”和“D”比较,大于它们,放到最右边,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/191d2969a3c84c1e9094660824f64d29.webp)
插入“F”,“F”大于“B”,往右子树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/27a41a1fd5aa4565a25b7179eb57af6e.webp)
“F”分别与“C”"D""E"比较,大于它们,放到最右边,此时触发分裂操作,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/31cc537cdd304b6193e5bbf656c1d421.webp)
选取待分裂节点的中值“D”,然后将中值“D”放到父节点中,父节点中的“B”小于“D”,于是放到“B”右边,而原来小于“D”的那些值作为左子树,原来大于“D”的那些值作为右子树。
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/4d74f13c5e0b48eebd038e69d9930a21.webp)
继续插入“M”,结果为,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/d92bead9817f4ac0a8876c4c3c3acaf0.webp)
插入“L’,大于“B”“D”,往右子树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/5b0e0695605b45499a73be336ea1db14.webp)
“L”大于“E”“F”小于“M”,于是放到第三个位置,此时触发分裂操作,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/d1ab65fc315c4f4a8a16c1fc3d6e842d.webp)
选取待分裂节点的中值“F”,然后将中值“F”放到父节点中,父节点中的“B”“D”都小于“F”,于是放到最右边,而原来小于“F”的那些值作为左子树,原来大于“F”的那些值作为右子树。
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/5b52dc3842e1404ca8ef482d51417387.webp)
插入“K”,结果为,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/36e376ae847742fbbd46578d91f7cf37.webp)
插入“J”,大于“B”“D”“F”,往右子树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/77e700daf2264607ba1d68cf6c419cf2.webp)
“J”小于“K”“L”“M”,于是放到第一个位置,此时触发分裂操作,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/326bbc7e8f224206ae52c57b41793d84.webp)
选取待分裂节点的中值“K”,然后将中值“K”放到父节点中,父节点中的“B”“D”“F”都小于“K”,于是放到最右边,而原来小于“K”的那些值作为左子树,原来大于“K”的那些值作为右子树。此时父节点也触发分裂操作,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/8de6ee6cff224ae896ea863d50577ce7.webp)
选取待分裂节点的中值“D”,然后将中值“D”放到父节点中,由于还没有父节点,那么直接创建一个新的父节点存放“D”,而原来小于“D”的那些值作为左子树,原来大于“D”的那些值作为右子树。
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/f54a50770214415a83d2cc87307e02bb.webp)
插入“I”,大于“D”,往右子树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/08801a9fbec040ba84e955d937fa97d9.webp)
右子树不是叶子节点,继续往下,这时“I”大于“F”而小于“K”,所以往第二个分支,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/e76ba0486fea44728cdfb3db5e5fe883.webp)
“I”小于“J”,于是放到左边,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/8e738993e0354ddcb0b5af419fcef24f.webp)
类似地,插入“H”,结果如下,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/77f92d3850ea43fa859c4114add2b330.webp)
插入“G”,往左子树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/8fd6165e0ec24398872765251cdd0f80.webp)
往中间分支,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/1eae12b11d5a46a6be00880ab2149045.webp)
触发分裂操作,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/6f5aeac7bcd146c39006e9037156823f.webp)
选取待分裂节点的中值“H”,然后将中值“H”放到父节点中,"H"大于父节点中的“F”而小于“K”,于是放到中间,而原来小于“H”的那些值作为左子树,原来大于“H”的那些值作为右子树。
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/134e7383082c469789bccb965adc60cc.webp)
综上所述,插入操作的核心是分裂操作。无需分裂的情况比较简单,直接插入即可;如果插入后超过节点容量,这个容量可预先自定义,则需要进行分裂操作,需要注意的是分裂可能引起父节点需要继续分裂。
查找
对B树进行查找就比较简单,查找过程有点类似二叉搜索树,从根节点开始查找,根据比较数值找到对应的分支,继续往子树上查找。
比如查找“I”,"I"大于“D”,往右子树,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/fe83337969e941258c85363f6eea6e9e.webp)
“I”分别与节点内值比较,大于“F”“H”而小于“K”,往第三个分支,
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/93ce19da3e2f4e47a401d4e54761f81d.webp)
逐一比较节点内的值,找到“I”。
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/84ebb8c3ddff41c18f21d7938314414f.webp)
-------------推荐阅读------------
我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)
跟我交流,向我提问:
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/1f79ffae8c1b405c9ffb27aca7f41a8a.webp)
欢迎关注:
![看图轻松理解数据结构与算法系列(B树)](https://img.blogweb.cn/article/76efc9d953c0414ab7bed3bfa2fcc2ce.webp)
转载自:https://juejin.cn/post/6844903666952978440