研究 B+ Tree 时发现,B+ Tree 的思想是逐步演化而来的。由二叉查找树 -> 平衡二叉树 -> 2-3 树 -> B 树演变而来;
二叉查找树是一个很典型的递归概念:
二叉树的查找效率与二叉树的结构有关,如果是平衡的二叉树,查找效率可以达到 logN,但极端条件下(如只有右子树的情况),则退化成单链表。
注:二叉树的根节点,是第一个插入到二叉树的节点,后续插入删除过程不会更新根节点;
注:2-3 树是一种比较复杂的数据结构,理解 2-3 树的主要作用,是为了理解红黑树。红黑树是对于 2-3 树的编码实现,并将 2-3 转换为二叉树的形式。
2-3 树最重要的性质就是**插入过程中实现自平衡。**对于插入操作,可以分为两种情况:
红黑树原本感觉很难,但发现本质上就是一个用红色表示 2 节点的 2-3 树,形式上仍旧使用普通二叉树的形式。这样既有了二叉树的操作,又有 2-3 树的高效率查询(logN);
注:2-3 树插入时的自平衡操作,被转换为红黑树的左旋、右旋、翻色 (filpColor) 操作;