树与存储

一个根节点，每个节点下挂着最多2个子节点。、

概念：

度：结点的分支数，二叉树度为2。

深度：树的层次。

二叉排序树：

二叉树的基础上，每个节点上都有一个数字，节点上的数字都比右节点上的大。

应用场景：

基于内存的排序数据结构，写入时将数据写入到对应的位置。数据可能会出现倾斜，可以想到数字写入顺序如果不是50-20-60-18-55，而是18-20-50-55-60，那么二叉树就会退变为链表。

B-树：

B-树每个节点上包含着数据和指针，每个指针指向其一个子节点的位置，并且数据的个数为指针的2d-1个。这里的d是指针的个数，同时也是树的“度”。

B-树的查找需要一次对每个节点进行二分查找，直至找到或返回null。通常，可以引入布朗过滤器等方式加速查找。

B-树的写入、删除时要进行分裂、合并、转移等操作，越是非顺序的插入就越容易碰到这些高性能消耗的操作。

应用场景：

一般B-树常常作为磁盘的查找的数据结构使用。

一般磁盘为了减少寻道时间，往往会进行预读，一次读入1个或多个page的数据。我们只要将B-树的每个节点控制在一个page大小，就可以保证，磁盘一次的查找只需要一次IO。一个page大小一般在4k，可以存储不少的数据，假设一个节点存储数据量为100，深度为3的B-树，即可保存100w数据量（100*100*100），而100的数据一般用不了4k的存储空间。

当然，这里节点中存储的东西主要包括data和指针，指针大小是固定的，而数据有大有小。只要控制好每个数据块的大小，就可以提高B-树的性能。

另外，一般情况下非叶子节点占用空间一般较小，上面的例子中，非叶子节点数据量只有1w，完全可以缓存至内存中，这点也是在实际数据库实现中常常使用到的优化。

B+树：

B+树完全是对B-树的工程级优化，非叶子节点不在存储data，只有根节点才存储数据。最大程度的加大了单个page中指针的个数，增加数的度。减少了树的层次。

另外相比较于B-树，其key的个数变为指针个数的2d个。

应用场景：

实际在数据库系统中使用时，往往每个叶子节点都会存储一个其相邻节点的一个指针，用来在范围查找时有更好的性能。