为了搞清楚索引为啥要用B+Tree就需要从链表开始的数据结构的各自优缺点，才可以更好的理解B+Tree。

链表，树，二叉树，二叉查找树，平衡二叉树(AVL树)，二三树，红黑树，B树，B+树

链表

好查询，但搜索效率查

树&二叉树

 

没有规律的树结构，没啥用，如果只要两个分支，就成为：二叉树

两个叉叉的二叉树，如果没有规律也没有

 二叉查找树（二叉搜索树，AVL树）

 

规律：左 < 中 < 右

如果插入顺序是有序的如：1,2,3，那么就是如下，对就是链表了。

 那就规定，左右子树高度差不能超过1，即：平衡

平衡二叉树

平衡二叉树，要想保持平衡就需要左旋和右旋，这个特别好性能。

为了解决这个问题，可以用二三树。二三树已经不是二叉树了。

二三树

二三树因为节点结构不统一，实现会很困难，二三树其实只是对二叉查找树的改进，为了实现一个相对平衡的改进。 

为了解决这个问题，进行二三节点进行着色，只需要保证三节点两边平衡就行。

红黑树

红黑树其实是一种相对平衡的树，即两边差距不要太大就行。但红黑树一个Node值存储一个节点，树节点总数是：2的0次方 + 2的1次方+2的2次方…… ，假设是完全二叉树。这不就是二进制位吗，（1,2,4,8,16,32,64,128,256,512,1024,2048,4096,8192）

 

如果存储1W数据呢？15层(2的15次方-1)

如果让一个节点存储多个数据呢，这样深度就能压缩。B树

B树

B树 B-Tree(不念B减Tree，就念B树)

深度是减下来了，但按照范围查询，读取数据是个问题。

想起来顺序列表读取数据效率不错，想着能否结合一下。 B+树

 B+树 

 也叫B+Tree

所有的数据都放在叶子节点

B+树是完全树，就是从左到右挨个排列

非叶子节点只是用来确定范围，找到了就按照列表来读取

 

---

END