二叉树,完全二叉树,平衡二叉树,二叉查找树,红黑树,B+ B- B*,LSM树的原理

前言 我们在平时的生产过程中,都知道涉及查询多的数据使用数组结构,涉及插入,删除操作多的数据使用链表结构,那么有没有一种兼顾两种的数据结构了,那么就是二叉树

###二叉树

二叉树结构: 此处输入图片的描述

二叉树定义:

完全二叉树

二叉查找树

平衡二叉树

平衡二叉树定义:

旋转操作 单旋转-双旋转

红黑树

B树(是一种多路搜索树,下面m指的是m阶B树)

B树的特性

1. 关键字集合分布在整颗树中;
2. 任何一个关键字出现且只出现在一个结点中;
3. 搜索有可能在非叶子结点结束;
4. 其搜索性能等价于在关键字全集内做一次二分查找;
5. 自动层次控制;

B+树

B*树

B树 B+树 B*树小结:

B树 多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点; 所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

B+树 在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点 中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

B*树 在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

TODO 未完待续