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

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

###二叉树

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

二叉树定义:

完全二叉树

二叉查找树

树的查找速度取决于树的高度

极端情况下的二叉查找树会使树退化成链表(如:有序数组的插入)

平衡二叉树

平衡二叉树定义:

旋转操作 单旋转-双旋转

红黑树

java中代表数据结构treeSet就是红黑树

B树(是一种多路搜索树,下面m指的是m阶B树,为了进一步降低树的高度)

无线多路的多路树又会导致结构退化成有序数组

B树的特性

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

文件系统和数据库索引都是存在硬盘的,如果数据量太大,不一定能一次性读取到内存。而通过每次加载B树的一个节点,然后一步步往下找、

B+树

由于数据都在叶子节点,而且叶子节点之间还是用指针形成了链表,所以很适合使用像数据库这种根据条件查询多条记录的文档系统

B*树

B树 B+树 B*树小结:

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

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

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

TODO 未完待续