[数据结构与算法]B-树，B+树，B*树

文件索引系统中应用
why?
数据量非常大-》在磁盘中存储-》会给数据创建索引-》给数据进行排序，加速搜索
需要解决两个问题？
1.减少磁盘的IO
2.更快的搜索算法

操作系统中，
管理内存是按照页page 4K 管理的
管理磁盘是按照block 16K

现在有n = 1000w个索引需要从磁盘中进行读取和搜索？
avl树和m为300的B-树？
avl树的高度：log2n = 24层
最差的情况一个节点只存储一个索引？最差需要24次磁盘IO
B-树高度：log(300)n = 3 层
最多花费3次磁盘IO

B+树

B+树是B-树的一种变形
非叶子结点只存储索引，不存储数据
B+树的叶子结点包含全部的关键字信息，而B-树的数据分散在各个结点当中。
叶子结点之间有指针链接，形成一个链表，可以进行顺序查找。

B+树存放的索引项相对于B-树能够存储的更多。

B*树

B*树是B+树的变体，在B+树的非根和叶子结点在增加指向兄弟结点的指针

B*提高了结点的利用率。