树结构的对比种类 #
- 二叉查找树
- 平衡二叉查找树
- B tree
- B + tree
二叉查找树 #
二叉查找树(Binary Search Tree)的特点是一个节点的左子树的所有节点都小于这个节点，右子树的所有节点都大于这个节点
查询和插入删除效率较高,但平衡性不佳,最坏情况下时间复杂度为O(n)
当每次插入的元素都是二叉查找树中最大的元素，二叉查找树就会退化成了一条链表，查找数据的时间复杂度变成了 O(n)
遍历 #
- 先序遍历按照“根节点->左子树->右子树”的顺序进行遍历
- 中序遍历按照“左子树->根节点->右子树”的顺序进行遍历
- 后序遍历按照“左子树->右子树->根结点”的顺序进行遍历
平衡二叉查找树 #
AVL树为实现平衡二叉查找树的数据结构
每个节点的左子树和右子树的高度差不能超过 1
时间复杂度降低到O(log n)
不管平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这就意味着磁盘 I/O 操作次数多，会影响整体数据查询的效率
B tree #
当树的节点越多的时候，并且树的分叉数 M 越大的时候，M 叉树的高度会远小于二叉树的高度
B + tree #
B+ 树的非叶子节点不存放实际的记录数据，仅存放索引，因此数据量相同的情况下，相比存储即存索引又存记录的 B 树，B+树的非叶子节点可以存放更多的索引，因此 B+ 树可以比 B 树更「矮胖」，查询底层节点的磁盘 I/O次数会更少
B+ 树所有叶子节点间还有一个链表进行连接，这种设计对范围查找非常有帮助