二叉树问题分析二叉树运行效率高，但也有问题，请看下面的二叉树二叉树需要加载成内存，如果二叉树的节点很少，没有什么问题，但是如果二叉树的节点很多（比如一亿个），就会出现以下问题：在构建二叉树的时候，多个需要I/O操作（数据库或文件中存在海量数据），存在海量节点。建造树时，速度很重要。大量的节点也会导致二叉树的高度非常大，从而降低运算速度。多叉树在二叉树中，每个节点都有一个数据项，最多有两个子节点。如果允许每个节点有更多的数据项和更多的节点，它就是一棵多路树。比如2-3树，2-3-4树就是多路树，多路树是重组节点，降低树的高度，可以优化二叉树。一个例子（下图2-3树）是一个多叉树B-tree的基本介绍B-Tree树就是B-tree，B是Balanced，意思是平衡。在mysql中，某类索引是基于B-tree或B+树的，如下图：2-3树的阶数为3，2-3-4树的阶数为4。B树搜索：从根节点开始，对该节点中的关键字（有序）序列进行二分查找，并命中则结束，否则进入查询关键字作用域的子节点；重复，直到对应的子指针为空，或者已经是叶节点。关键字集分布在整个树中，即叶子节点和非叶子节点都存储数据。搜索可能在非叶节点处结束。它的搜索性能相当于在键内对整个集合进行二分查找。B树通过重组节点，降低树的高度，减少I/O读写次数来提高效率。如图B所示，通过重组节点降低了树的高度。文件系统和数据库系统的设计者利用磁盘预读的原理，将一个节点的大小设置为一个页面（页面大小通常为4k），这样每个节点只需一次I/O就可以满载。设置树的度M（树中父节点包含最多子节点）为1024。在600亿个元素中，最多只需要4次I/O操作就可以读取到想要的元素。B树广泛应用于文件存储系统和数据库系统。B+树基本介绍B+树是B树的变种，也是一种多路搜索树。Non-leafnodehits），其性能相当于对全集关键字进行二分查找。所有关键字都出现在叶子节点的链表中（即数据只能在叶子节点中找到[也叫密集索引]），而链表中的关键字（数据）恰好是有序的。不可能命中非叶节点。非叶子节点相当于叶子节点的索引（稀疏索引），叶子节点相当于存储（关键字）数据的数据层。更适合文件索引系统。B树和B+树各有各的场景。不能说B+树就完全比B树好，反之亦然。B*树基本介绍B*树是B+树的一种变体，在B+树的非根非叶节点上增加了指向兄弟节点的指针。B树说明：*B*树定义非叶子节点关键字个数至少为(2/3)*M，即块的最小使用率为2/3，最小使用率为B+树的块是1/2。从第一个特征可以看出，B*树分配新节点的概率低于B+树，空间利用率更高。2-3树基本介绍（最简单的B树）2-3树是最简单的B树结构，具有以下特点：2-3树的所有叶子节点都在同一层。（只要B树满足这个条件）有两个子节点的节点称为第二节点，第二节点要么没有子节点，要么有两个子节点。具有三个孩子的节点称为三节点，三节点要么没有孩子，要么有三个孩子。2-3是由两个节点和三个节点组成的树。2-3棵树的插入规则：2-3棵树的所有叶子节点都在同一层。（只要B树满足这个条件）。有两个孩子的节点称为双节点，双节点要么没有孩子，要么有两个孩子。具有三个孩子的节点称为三节点，三节点要么没有孩子，要么有三个孩子。当按照规则向某个节点插入数字时，如果不能满足以上三个要求，则需要拆，先向上拆，如果上层已满，则拆当前层，以上三拆除后仍需满足条件。三节点子树的值的大小仍然满足（BST二叉排序树）的规则。
