最流行的存储结构之一是B树,许多开源数据库系统都是基于B树,
优点:增加节点扇出、减少树高和节点指针数量、降低平衡操作的频率。
二分搜索树
二分搜索树(BST)是一种有序的内存数据结构,可以高效地进行键值查找
![](https://i-blog.csdnimg.cn/direct/07441e94ab4c48ac974aa36fb5a45c52.jpeg)
![](https://i-blog.csdnimg.cn/direct/6b4330b97afd40bdac93249a25639004.jpeg)
树的平衡
防止所有元素都在树的一侧
树的平衡是通过以最小化树高并将每一边的节点数保持在界限内的方式重新组织节点来完成的
保持树的平衡方法之一是在添加或删除节点后执行旋转。
![](https://i-blog.csdnimg.cn/direct/085fb63a278f4ea0addd71a6bc85138c.jpeg)
层次结构
B树由多个节点组成。每个节点最多容纳N个键和N+1个指向子节点的指针。
根节点
根节点没有父节点,是树的顶端
叶定点
叶定点是没有子节点的底层节点