mysql优化 个人笔记 非礼勿扰 -m05

本文主要是介绍mysql优化 个人笔记 非礼勿扰 -m05，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一 、树

1. 树是一种递归数据结构，包含一个或多个数据节点的集合
   其中一个节点被定为树的根，而其余节点被称之为根的子代。
2. 除根节点以外的其他节点均被划分为多个非空集合，其中每个集合都称为子树
3. 节点与节点之间的关系 要么是父子节点 要么是兄弟节点
4. 一个节点可以有多个子节点 但是只能有一个父节点
   

根节点： 树中的最高节点 没有父节点
子树：根节点不为空 根节点的子树包含



叶子节点： 叶子节点是最低层的节点 叶子节点没有子节点
路径：到达一个点的路径 比如到达F 的路径是 A->B->F
度（Degree ）：一个节点的度 等于他的子节点数 比如D的度为2
在一个完全二叉树中 子节点的度都是0 其他节点的度都是2
层级：树一共有多少层 每个节点都属于某一个层

二 、二叉树

1. 二叉树每个节点最多有2孩子
2. 左子树也是二叉树
3. 右子树也是二叉树
   

三、严格二叉树

每个非叶子节点 都包含非空的左树和右数 也就是说除叶子节点外
其他节点的度（degree）都是2

四、完美perfect二叉树

1. 叶子节点都在最后一层
2. 所有非叶子节点的度（degree）都是2
   

五、完全complete二叉树

比完美二叉树差点

1. 所有子节点在倒数第一层 和 第二层
2. 所有节点 如果有一个子节点 一定是左子节点
   
   

六、二叉搜索树

1. 二叉搜索树节点以特定顺序排序，也称为有序二叉树
2. 左树所有节点 都小于根节点值
3. 右树所有节点都大于根节点的值
4. 所有左子树 右子树 也符合 第二条 第三条规则
   
   插入数据的过程：43, 10, 79, 90, 12, 54, 11, 9, 50
   

七、AVL树 平衡二叉树

1. 要么他是一棵空树
2. 要么他的左右俩子树的节点层级差值 不超过1
3. 所有子树 都是平衡二叉树
   平衡因子:某节点的左子树 和 右子树的深度（层级）差既为该节点的平衡因子
   平衡因子只能是 -1 ， 0 ， 1
4. 他在插入的时候可能会失去平衡 需要通过旋转来达到平衡
   旋转
   https://www.cs.usfca.edu/~galles/visualization/AVLtree.html
   https://www.javatpoint.com
   可以在这里做测试
   左左旋转

LL旋转 动态图

左右旋转：

LR 左右旋转 动态度

右右旋转：

RR 右右旋转 动态图

右左旋转

RL 右左旋转动态度

八、B树

1. B树中的每个节点最多包含m个子节点

2. 除了根节点和叶子节点 B树中的每个节点至少包含m/2个子节点

3. 根节点必须至少有2个子节点

4. 所有叶子节点 必须在同一层

5. B数 用于索引数据 并提供对磁盘上存储的实际数据的快速访问
   因为对存储在磁盘上的大型数据库中的值的访问非常耗时
   在最坏的情况下，搜索包含n个键值的未索引的未排序的数据库需要O(n)时间
   但是b数索引的话 最坏是O（logn)

   B数上执行某些操作 可能会违法B数的要求 为了维护B树 数可能会分裂&合并

搜索：
搜索与二叉树相似

搜索：601. 小于88  遍历88左子树2. 大于55 小于77 遍历 55 右子树3. 向右移动 找到60  4. 找到匹配项 返回
在B树中搜索取决于树的高度。搜索算法需要O（log n）时间来搜索B树中的任何元素。

插入

1.  遍历B数 找到可以插入的节点2. 如果节点块 节点数小于m-1 就将元素升序插入3. 如果节点块 节点数等于m-1 则执行	3.1 将元素升序插入	3.2 将节点块 拆分成2块 
	3.3 将中间值退给父节点	3.4 父节点执行插入流程 按照2 3 步骤拆分（如果需要）	 	

将元素46 插入一个4阶的B树中



删除元素

1. 找到元素2. 如果节点元素大于m/2 就直接删除3. 如果叶节点没有m/2个 从左右节点借元素	3.1  	如果左边节点大于m/2 就去把左边最大的给父节点 然后父节点摘一个元素给删除的子节点	3.2 如果左边不行 就右边  右边最小的给父节点 父节点摘一个元素给删除的子节点4. 如果左右都不行 那就只能新建一个节点 合并两个节点 和 父元素中连接两个节点的元素

3.1 左节点大于m/2
假设4阶 删除 58

3.2 右节点大于m/2 与左节点差不多
**3.2 左右都不大于m/2 **
假设5阶 删除55

九、B+树

我理解 B+树 与B树的区别在于

1. B+数 把数据都存储在叶子节点 而其他节点都用来存储键（索引）
2. 叶子节点都连起来了 链表
   
   优势：
   1. 可以在相同数量磁盘访问中提取记录
   2. 树的高度保持平衡 且 比较小
   3. 用于索引比较多（比如：mysql）
   4. 数据仅存储在叶子节点 所以搜索速度很快

这篇关于mysql优化 个人笔记 非礼勿扰 -m05的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！