二叉树存在的问题
- 二叉树需需要加载到内存,如果二叉树的结点很多就会出现如下问题:
- 在构建二叉树时,需要多次进行I/O操作,结点海量,构建二叉树时,速度有影响
- 结点海量,也会造成二叉树的高度很大,会降低操作速度
- 多叉树
- 在二叉树中,每个节点有数据项,最多有两个结点。如果允许每个接地那可以有更多的数据项和更多的结点,那就是多叉树。
- 多叉树通过重新组织结点,减少树的高度,能对二叉树进行优化。
- B树通过重新组织结点,降低了树的高度
- 文件系统及数据库系统的设计者利用了磁盘预读原理,将一个结点的大小设为等于一个页(页的大小通常是4K),这样每个节点只需要一次I/O就可以完全载入
- 将树的度M设置为1024,在600亿个元素中最多只需要4次I/O操作就可以读取到想要的元素,B树广泛用于文件存储系统以及数据库系统中。
2-3树
2-3树是最简单的B树结构,具有如下特点: (1) 2-3树的所有结点都在同一层(只要是B树都满足这个条件) (2) 有两个子结点的结点叫做二节点,二节点要么没有子结点要么有两个子结点 (3) 有三个子结点的结点叫做三节点,三节点要么没有子结点要么有三个子结点 (4) 2-3树是由二节点和三节点构成的树
- 2-3树的插入规则
- 2-3树的所有叶子结点都在同一层(只要是B树均满足这个条件)
- 有两个子结点的结点叫做二节点,二节点要么没有子结点要么有两个子结点
- 有三个子结点的结点叫做三节点,三节点要么没有子结点要么有三个子结点
- 当按照规则插入一个树到某个节点时,不能满足上述三个要求,就需要拆,先向上拆,如果上层满,则拆本层,拆后需要满足上面三个条件。
- 对于上三节点的子树的值的大小仍遵守二叉排序树的规则。
- B树的说明:
- B树的阶:结点的最多子结点个数。如2-3树的阶是3
- B-树的搜索,从根结点开始,对结点内的关键字进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子节点;重复,直到所对应的儿子指针为空,或已经是叶子结点
- 关键字集合分布在整棵树中,即叶子结点和非叶子结点都存放数据
- 搜索有可能在非叶子结点结束
- 其搜索心梗等价于在关键字全集内做一次二分查找