首页  思维导图  详情

SpringCloud学习笔记

2023-12-14 21:07:09   0  举报





仅支持查看

AI智能生成

SpringCloud学习笔记

spring

springcloud

作者其他创作

大纲/内容

数据结构

数组

链表

单向链表

双向链表

循环链表

跳表

在普通链表上简历索引

哈希

一致性哈希

队列

栈

树

红黑树

五个特性

根节点是黑色

叶子节点（NIL）是黑色

从根节点到叶子节点黑色节点的个数相同

节点为黑色或者红色

红色节点的两个子节点为黑色

优点

并不追求“完全平衡”——它只要求部分地达到平衡要求，降低了对旋转的要求，从而提高了性能。

二叉搜索树

b树

定义

1.定义任意非叶子结点最多只有M个儿子；且M>2；

2.根结点的儿子数为[2, M]；

3.除根结点以外的非叶子结点的儿子数为[M/2, M]；

4.每个结点存放至少M/2-1（取上整）和至多M-1个关键字；（至少2个关键字）

5.非叶子结点的关键字个数=指向儿子的指针个数-1；

6.非叶子结点的关键字：K[1], K[2], …, K[M-1]；且K[i] < K[i+1]；

7.非叶子结点的指针：P[1], P[2], …, P[M]；其中P[1]指向关键字小于K[1]的子树，P[M]指向关键字大于K[M-1]的子树，其它P[i]指向关键属于(K[i-1], K[i])的子树；

8.所有叶子结点位于同一层；

特性

1.关键字集合分布在整颗树中；

2.任何一个关键字出现且只出现在一个结点中；

3.搜索有可能在非叶子结点结束；

4.其搜索性能等价于在关键字全集内做一次二分查找；

5.自动层次控制；

b+树

定义

其定义基本与B-树同，除了：

1.非叶子结点的子树指针与关键字个数相同；

2.非叶子结点的子树指针P[i]，指向关键字值属于[K[i], K[i+1])的子树（B-树是开区间）；

3.为所有叶子结点增加一个链指针；

4.所有关键字都在叶子结点出现；

特性

1. 所有关键字都出现在叶子结点的链表中（稠密索引），且链表中的关键字恰好是有序的；

2.不可能在非叶子结点命中；

3. 非叶子结点相当于是叶子结点的索引（稀疏索引），叶子结点相当于是存储（关键字）数据的数据层；

4.更适合文件索引系统；

b树和b+树区别

B树中同一键值不会出现多次，并且它有可能出现在叶结点，也有可能出现在非叶结点中。而B+树的键一定会出现在叶结点中，并且有可能在非叶结点中也有可能重复出现，以维持B+树的平衡

因为B树键位置不定，且在整个树结构中只出现一次，虽然可以节省存储空间，但使得在插入、删除操作复杂度明显增加。B+树相比来说是一种较好的折中。

B树的查询效率与键在树中的位置有关，最大时间复杂度与B+树相同(在叶结点的时候)，最小时间复杂度为1(在根结点的时候)。而B+树的时候复杂度对某建成的树是固定的

B*树

定义

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针；

特性

B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3

b*和b+的区别

B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分 数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的 关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点 与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增 加新结点的指针；所以，B*树分配新结点的概率比B+树要低，空间使用率 更高；

AVL树

定义

相比于”二叉查找树”，它的特点是：AVL树中任何节点的两个子树的高度最大差别为1。

失去平衡的可以概括为4种姿态

左左

左子树的左子树导致的失衡

左右

左子树的右子树导致的失衡

右左

右子树的左子树导致的失衡

右右

右子树的右子树导致的失衡