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*提高了结点的利用率。