二叉树的局限性

我们知道二叉树的查询速度十分高效，为了避免树的链化，也有平衡二叉树等可用来保持高效的查询。通常查询时间都是O(logn)。

但是无论是什么二叉树，都有一个很关键的问题：二叉

每个节点最多只能有两个子节点，这就意味着如果使用二叉树来存储海量数据的话，树的深度是很深的，比如一个深度为10的满二叉树，它的叶子节点最多也只能存储512个数据。

这样我们查询一个叶子节点的数据，每一层都进行一次磁盘IO操作，到了叶子节点，就需要10次IO操作。如果需要存储的数据更多，二叉树的深度就更深，IO操作也需要更多。

所以二叉树“高瘦”类型并不是索引所需要的数据结构。

B树
和“高瘦”类型对应的，就是“矮胖”类型，对应的“N”叉树站了出来。

B树（Balance Tree），也叫平衡的多路搜索树。文件系统和数据库系统的索引数据结构通常用它来实现。

B树的每一个节点，最多可以包括N个节点，N称为B树的“阶”。