漫画：什么是B-树？

妖狐艹你老母 2023-05-28 14:27 49阅读 0赞

![format_png][]

![format_png 1][]

![format_png 2][]

![format_png 3][]

————————————

![format_png 4][]

![format_png 5][]

![format_png 6][]

![format_png 7][]

![format_png 8][]

![format_png 9][]

![format_png 10][]

![format_png 11][]

![format_png 12][]

————————————

![format_png 13][]

![format_png 14][]

![format_png 15][]

![format_png 16][]

![format_png 17][]

![format_png 18][]

![format_png 19][]

![format_png 20][]

![format_png 21][]

![format_png 22][]

![format_png 23][]

![format_png 24][]

![format_png 25][]

![format_png 26][]

二叉查找树的结构：

![format_png 27][]

第1次磁盘IO：

![format_png 28][]

第2次磁盘IO：

![format_png 29][]

第3次磁盘IO：

![format_png 30][]

第4次磁盘IO：

![format_png 31][]

![format_png 32][]

![format_png 33][]

![format_png 34][]

![format_png 35][]

下面来具体介绍一下B-树（Balance Tree），一个m阶的B树具有如下几个特征：

1.根结点至少有两个子女。

2.每个中间节点都包含k-1个元素和k个孩子，其中 m/2 <= k <= m

3.每一个叶子节点都包含k-1个元素，其中 m/2 <= k <= m

4.所有的叶子结点都位于同一层。

5.每个节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域分划。

![format_png 36][]

![format_png 37][]

![format_png 38][]

![format_png 39][]

![format_png 40][]

![format_png 41][]

![format_png 42][]

第1次磁盘IO：

![format_png 43][]

在内存中定位（和9比较）：

![format_png 44][]

第2次磁盘IO：

![format_png 45][]

在内存中定位（和2，6比较）：

![format_png 46][]

第3次磁盘IO：

![format_png 47][]

在内存中定位（和3，5比较）：

![format_png 48][]

![format_png 49][]

![format_png 50][]

![format_png 51][]

![format_png 52][]

![format_png 53][]

自顶向下查找4的节点位置，发现4应当插入到节点元素3，5之间。

![format_png 54][]

节点3，5已经是两元素节点，无法再增加。父亲节点 2， 6 也是两元素节点，也无法再增加。根节点9是单元素节点，可以升级为两元素节点。于是**拆分**节点3，5与节点2，6，让根节点9升级为两元素节点4，9。节点6独立为根节点的第二个孩子。

![format_png 55][]

![format_png 56][]

![format_png 57][]

![format_png 58][]

自顶向下查找元素11的节点位置。

![format_png 59][]

删除11后，节点12只有一个孩子，不符合B树规范。因此找出12,13,15三个节点的中位数13，取代节点12，而节点12自身下移成为第一个孩子。（这个过程称为**左旋**）

![format_png 60][]

![format_png 61][]

![format_png 62][]

![format_png 63][]

![format_png 64][]

![format_png 65][]

[format_png]: /images/20230528/ee4be37806ab42f49803f4e8114a95bf.png
[format_png 1]: /images/20230528/1e783c9b9f6440bf81e37475e52013ba.png
[format_png 2]: /images/20230528/e2ae7e2444754484a13e88aecac520af.png
[format_png 3]: /images/20230528/f55f2b5c1d584aaf90f60387e9d9c598.png
[format_png 4]: /images/20230528/e90393a971ef423e99ae417fb07804e2.png
[format_png 5]: /images/20230528/11d27417e18946c6a39e7f04741372ae.png
[format_png 6]: /images/20230528/65a9ec24041845738b448abdcb37d9ec.png
[format_png 7]: /images/20230528/8ebdcdf6baac4caeb66c86d39331946f.png
[format_png 8]: /images/20230528/496a00dce6ad4f968e4a5398bf2bc1ac.png
[format_png 9]: /images/20230528/f3d26586f7084670aa074846d015dc80.png
[format_png 10]: /images/20230528/0baf674d1e464a228b997ddf5218fd42.png
[format_png 11]: /images/20230528/5424a5ad92fb4667b9b87ae997bd4e3f.png
[format_png 12]: /images/20230528/8c8afba0191a41b4b23ad79fe2bd0d79.png
[format_png 13]: /images/20230528/47c0e2e99c0b49208d2a4da7d45d6c32.png
[format_png 14]: /images/20230528/dd46d0e1a76a4e6fb5c07f9885141fdb.png
[format_png 15]: /images/20230528/1b8510142def4f28a08a3a6cf3ccc8f2.png
[format_png 16]: /images/20230528/448527c6a00b44fa87b492e669e57ec1.png
[format_png 17]: /images/20230528/8e6f23a57cde470cb6947d62eb58de0b.png
[format_png 18]: /images/20230528/e6748566479043fd8b285ce4fdc0c11a.png
[format_png 19]: /images/20230528/7ddd0bbc520044a4bf66c284a27d9216.png
[format_png 20]: /images/20230528/38615e12e9de4e85ac8bdec78c15f5d7.png
[format_png 21]: /images/20230528/c4c82cf0203e4bd98b946906c0d1beb1.png
[format_png 22]: /images/20230528/df93d9e942a0478b9850ce79e40833ca.png
[format_png 23]: /images/20230528/df5225ab0c254b5697a60b4b3b71c838.png
[format_png 24]: /images/20230528/fd22e3850c9f44e4a7ee407a8f97d29d.png
[format_png 25]: /images/20230528/31b8a02898fe4b048b391efb9aea6c59.png
[format_png 26]: /images/20230528/c602dbcd685048a4ad048ac42053a56c.png
[format_png 27]: /images/20230528/1f3a2903e87947ebbb58722c59035a80.png
[format_png 28]: /images/20230528/247237770805461b8fdc09916dd224f2.png
[format_png 29]: /images/20230528/e9c80fe345eb4562900ee694f0db1b20.png
[format_png 30]: /images/20230528/caed4730ccf041cfae822c7a02098175.png
[format_png 31]: /images/20230528/4c1b985d1afd48a69cd4858238d17c46.png
[format_png 32]: /images/20230528/9e6bd7f590c541d192b4f6930cc6d1e9.png
[format_png 33]: /images/20230528/04d8833d5a5a41cf949aaee859d3347b.png
[format_png 34]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29CcUVneHZpYnlaM1MyTzhHRzJFY2lic21SeTJ1cUU1ZFB0UlNiaElKNGNpYVpUTUdEM2R6RFlUQVFFVFhHYTN6eGowQWRMZkZwaGhDdEEvNjQw?x-oss-process=image/format,png
[format_png 35]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29CcUVneHZpYnlaM1MyTzhHRzJFY2lic2licUhlVEluOWhpYmMzR0pHaWFyU1M5eEgwU3BQaGFjbFF2S0JZeTVuYm1UZzFjWW5KTTNBRmZwZy82NDA?x-oss-process=image/format,png
[format_png 36]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29CcUVneHZpYnlaM1MyTzhHRzJFY2lic2prU3hjS0dSekdtSjNpYXhrQkFuYzB2cU9mVG4ybk1KV1RRTElDTkZoOGY0UzhUZVZwemVYNncvNjQw?x-oss-process=image/format,png
[format_png 37]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29CcUVneHZpYnlaM1MyTzhHRzJFY2lic0J4OEFvZVVhOUlWYmsySmJkc2pNWjVwMHRkaWNIa082Zk42ZENJd2RJb2preGljSzRHZEF2N1hRLzY0MA?x-oss-process=image/format,png
[format_png 38]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR29CcUVneHZpYnlaM1MyTzhHRzJFY2liczVMRlh4TFJoRVZINTVtcVhNaEdmOUMyaWNaNGlhRmNCaFVoQUJUaHZHMGhpYW9EMXo0aWNnUUpiYkEvNjQw?x-oss-process=image/format,png
[format_png 39]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSU1FiNmVEeFpjdGJBeHZOdDVnWUtQbEZFaWFOYVBjcW9yMmhKNnBleXV4R1FEbVE4R2FvdWdpYncvNjQw?x-oss-process=image/format,png
[format_png 40]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSaWN0SkduNmF4RWozQk1iYzVSd0JpYUFQUEM5bVd4WWw2eWhROGljQjFZQW51eDM3Tm1ZaWF0S1FYUS82NDA?x-oss-process=image/format,png
[format_png 41]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSd0hYQVM1QjVpY0dQOThDaFl5Q1EzamlhdzdpY2tlaWJSQmliWlR0dTVId1dNMzBSMTVWQWJDaDR0T1EvNjQw?x-oss-process=image/format,png
[format_png 42]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSeFo2dlpqY2xOV0E0MGNpYm1aQWljOVpaWWVaVDRhT2liQ1pWVEFjNENhYXVYSk43NlV2RGI3bTNRLzY0MA?x-oss-process=image/format,png
[format_png 43]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSQ0NkUVBqeFZCNTMxUVlsdGliWWliWUlvNmlhbGliNmJnOHNYSk9CT2VpY0R2RVV2bmlhc3R3aWNpYmFlaWJnLzY0MA?x-oss-process=image/format,png
[format_png 44]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSSWlhc1V2eE9zOWlidmx1NFBQNGd0UFptQWJoRVZpY2gxdHBqYTFQRFdlSHl4NTQ5MUo5YkxFMTJBLzY0MA?x-oss-process=image/format,png
[format_png 45]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSNGNjR1JFWHpmanp0QTk4cDBiNGRJQ3JMQVhyc2licVlhUVU1TVJlell1QWNoSGxwZGw5TUl6dy82NDA?x-oss-process=image/format,png
[format_png 46]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSS2Y4WFF5dFIzWDlCMzIxTmt2YThGb3Z6bjlGbW45NUhaUDRvSzFJbDdhRkZ0Q2R5aEhmZlV3LzY0MA?x-oss-process=image/format,png
[format_png 47]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSTXFySUNpYUhFSDJ1Y3d0YlNnaDRBVDN1c09POThBeHYzbXdIR1dPZWEyR2tKUTc3U3Z4ZnM1Zy82NDA?x-oss-process=image/format,png
[format_png 48]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSdThMakFxdGFneWVpY1kyN3lhVUcwU21tTFFMQ09QM1ZRclFOSWVNQ2F4ZmliWTZQcGljdUYxdHlnLzY0MA?x-oss-process=image/format,png
[format_png 49]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FST2pYTW14RGNEcDQ3REJjdU9SYnBNbnhnNTByc0JROTZDTjFWOGt4TDJaN0tqc2dKQ2w1ZGlhdy82NDA?x-oss-process=image/format,png
[format_png 50]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSWTdmbnRuN1VGZ2ljUlVyakhhRDBiZG1XVll3VkZIYmN4WU5WY2liU2VXSVhiaGlhQW9WemNjRWlhUS82NDA?x-oss-process=image/format,png
[format_png 51]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSemxoUmNlaWE2UWVQUHRHbHhYY2hwRmxsQTVQajJ1eGljd0pHUU5MaWFKUWNpY0ROWVEzcHRucW4yZy82NDA?x-oss-process=image/format,png
[format_png 52]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSWHBpY2ZKM1RlVHBLaWEzUTNPOGcyR3ZlZWlhZFBwR1FMVTRMQXQ0aE5DS3JhMWZGU2xIVHZDV053LzY0MA?x-oss-process=image/format,png
[format_png 53]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSSzRLZDFyQ2NHaWNUbHR6bHpWRlVXaWJsYXRpYkx5MnJZZmlhWXJDS3d2OElYYjhlZ2FiZ1hKZ1dKZy82NDA?x-oss-process=image/format,png
[format_png 54]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSWWs1ZXVEcmJNZ1Z1YlRSNGd2SUwzVTRMZGljSzNGdTFmN0FUcTl0R0NoTDlZTFhpYkpldUNUQ0EvNjQw?x-oss-process=image/format,png
[format_png 55]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSU0JxT0tRYzNOWWU4SEE3bVg0UWpTalVwZmtXTHFHQmZXbTh3SG1pYzdxYWpGYWlja0dTVFg4TkEvNjQw?x-oss-process=image/format,png
[format_png 56]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSOXYyaDI1aHpuMTkyWHVxaWNvVVZDV0lCRXQ2Z0tSb2N1alh6REppYW1yZ2liMUVWMWliU3B4TlFVQS82NDA?x-oss-process=image/format,png
[format_png 57]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSYnRQZXFCdEZ2WG5lWGxpY3k3YVBSV2lhUTU5Z29UanlDQW1uWDF0VFEwS2xZMjROYk14dGZGMHcvNjQw?x-oss-process=image/format,png
[format_png 58]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSbUM3TkxHM0hVWm9xcHZQMzBVRFNNVGowV053b1VZaGFrWU5pYkFRYVVsS2ljbGljdnlNTnQzYkdBLzY0MA?x-oss-process=image/format,png
[format_png 59]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSZm5Hd1BHclg0Tmhua0pmQnVLcU5kWEF5SFdKaWFCZDViMHJ1aWJ1aEhKdlVubUNZcHQxZUp4ZGcvNjQw?x-oss-process=image/format,png
[format_png 60]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSdGE5Yk93QU5BMWdqemR1V0tLQWhsNU45SWtGZ1pQTllOTnp6ZEJ5WTdMWWlhdXRMWFZObko0dy82NDA?x-oss-process=image/format,png
[format_png 61]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSYkRPQTJTWWhrc1VPM0JsaWJnWmNpYXV4Y1RaRmZYb2JDbkZ3UGVnVWpMSFlxd3E0Q1c3Z1RZR2cvNjQw?x-oss-process=image/format,png
[format_png 62]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSSkwzRWNOT2ljMGZIYWZuNGx0eUludWdQWThqdGlhVWtmUVdNWU9pYTN6Y3NxRW1pYlo3eHN6c3Z2dy82NDA?x-oss-process=image/format,png
[format_png 63]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSZGtNWUtwUjRPTVdmd0xWRWp5VlRGdk4yNDdGeUx1MnhoNnRpYUFhWkhMcTNDZHRicEhKTkNpY1EvNjQw?x-oss-process=image/format,png
[format_png 64]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSRE52N0VxTWdzRUJ2QmliT0RralcyaWFPOGliMnBPdkJsYXJzbVhLM2JWUFRKY3FDVjZxUzl5VHFBLzY0MA?x-oss-process=image/format,png
[format_png 65]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9tbWJpei5xcGljLmNuL21tYml6X2pwZy9OdE81c2lhbEpaR3JiSTgzZjhtZVluMVVsemliSEdCY3FSOWU3MTdRdEE4UFNzRnZrV253anM5SHVJMjhtYnBtdmFMRkZmU2lha0FsZm5vdHZkWjBnaWJBcEEvNjQw?x-oss-process=image/format,png