树

二叉树、二叉查找树、2-3查找树、字典树（trie树）、平衡树（AVL树）、红黑树、B~树（B树、B+树、B*树）、R树…
网上的资料过于复杂，且发现很多错误，所以打算自己重新总结一次。

B~树

插入或者删除元素都会导致节点发生裂变反应，有时候会非常麻烦，但正因为如此才让B树能够始终保持多路平衡，这也是B树自身的一个优势：自平衡；B树主要应用于文件系统以及部分数据库索引，如MongoDB，大部分关系型数据库索引则是使用B+树实现。

B树

最坏的情况下磁盘IO的次数由树的高度来决定，减少磁盘IO的次数就必须要压缩树的高度，让瘦高的树尽量变成矮胖的树，所以B-Tree就这样诞生了。

m阶B-Tree满足以下条件：

1. 每个节点最多拥有m个子树
2. 根节点至少有2个子树
3. 分支节点至少拥有m/2颗子树（除根节点和叶子节点外都是分支节点）
4. 所有叶子节点都在同一层、每个节点最多可以有m-1个key，并且以升序排列

B+树

B+Tree是B树的变种，有着比B树更高的查询性能，来看下m阶B+Tree特征：

1、有m个子树的节点包含有m个元素（B-Tree中是m-1）

2、根节点和分支节点中不保存数据，只用于索引，所有数据都保存在叶子节点中。

3、所有分支节点和根节点都同时存在于子节点中，在子节点元素中是最大或者最小的元素。

4、叶子节点会包含所有的关键字，以及指向数据记录的指针，并且叶子节点本身是根据关键字的大小从小到大顺序链接。

B+树的优势：
1.单节点可以存储更多的元素，使得查询磁盘IO次数更少。
2.所有查询都要查找到叶子节点，查询性能稳定。

1. 更加高效的单元素查找
2. 叶子节点形成有顺链表，范围查找性能更优

   B*树

参考资料：

什么是B-Tree：https://www.cnblogs.com/dongguacai/p/7239599.html
什么是B+Tree：https://www.cnblogs.com/dongguacai/p/7241860.html

赏

谢~

支付宝

微信