MySQL 索引原理 B+ 树，java 学习视频百度云盘
二叉查找树可以任意地构造，同样是 2,3,5,6,7,8 这六个数字，也可以按照下图的方式来构造：
但是这棵二叉树的查询效率就低了。因此若想二叉树的查询效率尽可能高，需要这棵二叉树是平衡的，从而引出新的定义——平衡二叉树，或称 AVL 树。
如果在 AVL 树中进行插入或删除节点，可能导致 AVL 树失去平衡，这种失去平衡的二叉树可以概括为四种姿态：LL（左左）、RR（右右）、LR（左右）、RL（右左）。它们的示意图如下：
这四种失去平衡的姿态都有各自的定义：
LL：LeftLeft，也称“左左”。插入或删除一个节点后，根节点的左孩子（Left Child）的左孩子（Left Child）还有非空节点，导致根节点的左子树高度比右子树高度高 2，AVL 树失去平衡。
RR：RightRight，也称“右右”。插入或删除一个节点后，根节点的右孩子（Right Child）的右孩子（Right Child）还有非空节点，导致根节点的右子树高度比左子树高度高 2，A
VL 树失去平衡。
LR：LeftRight，也称“左右”。插入或删除一个节点后，根节点的左孩子（Left Child）的右孩子（Right Child）还有非空节点，导致根节点的左子树高度比右子树高度高 2，AVL 树失去平衡。
RL：RightLeft，也称“右左”。插入或删除一个节点后，根节点的右孩子（Right Child）的左孩子（Left Child）还有非空节点，导致根节点的右子树高度比左子树高度高 2，AVL 树失去平衡。
AVL 树失去平衡之后，可以通过旋转使其恢复平衡。下面分别介绍四种失去平衡的情况下对应的旋转方法。
LL 的旋转。LL 失去平衡的情况下，可以通过一次旋转让 AVL 树恢复平衡。步骤如下：
将根节点的左孩子作为新根节点。
将新根节点的右孩子作为原根节点的左孩子。
将原根节点作为新根节点的右孩子。
LL 旋转示意图如下：
RR 的旋转：RR 失去平衡的情况下，旋转方法与 LL 旋转对称，步骤如下：
将根节点的右孩子作为新根节点。
将新根节点的左孩子作为原根节点的右孩子。
将原根节点作为新根节点的左孩子。
RR 旋转示意图如下：
LR 的旋转：LR 失去平衡的情况下，需要进行两次旋转，步骤如下：
围绕根节点的左孩子进行 RR 旋转。
围绕根节点进行 LL 旋转。
LR 的旋转示意图如下：
RL 的旋转：RL 失去平衡的情况下也需要进行两次旋转，旋转方法与 LR 旋转对称，步骤如下：
围绕根节点的右孩子进行 LL 旋转。
围绕根节点进行 RR 旋转。
RL 的旋转示意图如下：
二、平衡多路查找树（B-Tree）
B-Tree 是为磁盘等外存储设备设计的一种平衡查找树。因此在讲 B-Tree 之前先了解下磁盘的相关知识。
系统从磁盘读取数据到内存时是以磁盘块（block）为基本单位的，位于同一个磁盘块中的数据会被一次性读取出来，而不是需要什么取什么。
InnoDB 存储引擎中有页（Page）的概念，页是其磁盘管理的最小单位。InnoDB 存储引擎中默认每个页的大小为 16KB，可通过参数 innodb_page_size 将页的大小设置为 4K、8K、16K，在 MySQL 中可通过如下命令查看页的大小：
mysql> show variables like 'innodb_page_size';
而系统一个磁盘块的存储空间往往没有这么大，因此 InnoDB 每次申请磁盘空间时都会是若干地址连续磁盘块来达到页的大小 16KB。InnoDB 在把磁盘数据读入到磁盘时会以页为基本单位，在查询数据时如果一个页中的每条数据都能有助于定位数据记录的位置，这将会减少磁盘 I/O 次数，提高查询效率。
B-Tree 结构的数据可以让系统高效的找到数据所在的磁盘块。为了描述 B-Tree，首先定义一条记录为一个二元组[key, data] ，key 为记录的键值，对应表中的主键值，data 为一行记录中除主键外的数据。对于不同的记录，key 值互不相同。
一棵 m 阶的 B-Tree 有如下特性：
1. 每个节点最多有 m 个孩子。
2. 除了根节点和叶子节点外，其它每个节点至少有 Ceil(m/2)个孩子。
3. 若根节点不是叶子节点，则至少有 2 个孩子
4. 所有叶子节点都在同一层，且不包含其它关键字信息
5. 每个非终端节点包含 n 个关键字信息（P0,P1,…Pn, k1,…kn）
6. 关键字的个数 n 满足：ceil(m/2)-1 <= n <= m-1
还未添加个人签名 2021.03.18 加入
还未添加个人简介
评论