B和B+树的的理解

一、B树：

B树

（1）、每个节点存储多个元素
（2）、摒弃二叉树结构，采用多叉树
它是一种多路搜索树，它的每个节点可以拥有多余两个的孩子节点，M路的B树最多可以拥有M路孩子节点。这样设计主要是为了降低它的高度。但也不能无限多路，那样就成了一个一维数组了，一般用在文件索引的地方比较多。

那么为什么文件系统不用红黑树之类的呢？

如果用红黑树存储，增加或者减少文件时红黑树需要做旋转之类的操作来保持平衡，那么就需要把所有节点都加载到内存中，查找时也需要全部加载到内存，所以不适合。然而用B树的多路存储就没有这个压力，并且查找的时候只需要一个节点一个节点的往下查找就可以了。

二、B+树

B+树

B+树是在B树的基础上改造的，它的数据都在叶子节点上，同时，叶子节点之间还加了指针形成链表。
B+树在数据库的索引中用得比较多，如果需要查询多条数据，B树需要做局部的中序遍历，可能要跨层访问。而B+树由于所有数据都在叶子结点，不用跨层，同时由于有链表结构，只需要找到首尾，通过链表就能把所有数据取出来了。
这也是为什么没有在数据库中用hash的原因，查找一个数hash更快，但是多个数字的时候就没有B+数快了。