mysql 存储结构的进化之路

---

媒介

树形结构是一种具有条理关系的数据结构，它通常用于表现具有父子关系或层级关系的数据。在盘算机科学中，树形结构广泛应用于文件体系、数据库索引、XML/JSON分析、搜索引擎索引等场景。通过不绝进化，mysql末了构造出B+Tree作为存储结构。

---

一、线性结构

线性结构（如数组、链表）是盘算机科学中最根本的数据结构，它们以线性方式构造数据。然而，劈面临更为复杂的题目时，线性结构的范围性渐渐表现。

为相识决线性结构的范围性，盘算机科学家开始探索多维的数据构造方式，树形结构应运而生。树形结构通太过层和分支的方式，可以大概更精确地模拟现实天下中的复杂关系。
二、二叉树（BST）

二叉树的特性
左子树全部的节点都小于父节点，右子树全部的节点都大于父节点。投影到平面以后，就是一个有序的线性表。

但是二叉查找树有一个题目:
就是它的查找耗时是和这棵树的深度相干的，在最坏的环境下时间复杂度会退化成O(n)
假设插入的数字为 2-4-6-8-12-16，此时的树形结构为

酿成了一个一边倒的斜树，也就是链表，查找的时间和链表是一样的时间，复杂度酿成O(n)。
造成这个征象是由于不能主动平衡，于是盘算机科学家开始举行升级–平衡二叉树
三、平衡二叉树（AVL）

AVL的每个节点的左子树和右子树的高度差（平衡因子）只能是-1、0或1。查找、插入和删除操纵的时间复杂度均为O(log n)，此中n为树中节点的数量
比方下图，左侧的是AVL，右侧则不是AVL（高度差 > 1）

那怎样包管二叉树的平衡呢？旋转操纵与维护平衡
旋转操纵：

• 为了规复平衡二叉树的平衡性，须要举行旋转操纵。旋转操纵包罗左旋、右旋、左右双旋和右左双旋等。
  
• 左旋操纵将节点的右子树提升为新的根节点，并将原根节点降为新的左子节点。右旋操纵则相反。
  
• 双旋操纵是在一次左旋或右旋的根本上再举行一次右旋或左旋，以规复树的平衡性。
  
• 
  

维护平衡：

• 在举行插入或删除操纵时，须要实时查抄树的平衡性。一旦发现不平衡，就立即找到最小不平衡子树，并对其举行旋转操纵以规复平衡。
  
• 旋转操纵不但改变了节点的位置关系，还调解了节点的平衡因子和子树的高度。
  

比方：下面的树插入了14后，深度差大于1，此时须要右旋再左旋来天生新的AVL

代码实现：

1. class TreeNode {
2.     int key;
3.     int height;
4.     TreeNode left, right;
6.     TreeNode(int d) {
7.         key = d;
8.         height = 1;
9.     }
10. }
12. class AVLTree {
13.     TreeNode root;
15.     // 右旋
16.     TreeNode rightRotate(TreeNode y) {
17.         TreeNode x = y.left;
18.         TreeNode T2 = x.right;
20.         // 进行右旋
21.         x.right = y;
22.         y.left = T2;
24.         // 更新高度
25.         y.height = Math.max(height(y.left), height(y.right)) + 1;
26.         x.height = Math.max(height(x.left), height(x.right)) + 1;
28.         // 返回新的根
29.         return x;
30.     }
32.     // 左旋
33.     TreeNode leftRotate(TreeNode x) {
34.         TreeNode y = x.right;
35.         TreeNode T2 = y.left;
37.         // 进行左旋
38.         y.left = x;
39.         x.right = T2;
41.         // 更新高度
42.         x.height = Math.max(height(x.left), height(x.right)) + 1;
43.         y.height = Math.max(height(y.left), height(y.right)) + 1;
45.         // 返回新的根
46.         return y;
47.     }
49.     // 获取高度
50.     int height(TreeNode N) {
51.         if (N == null)
52.             return 0;
54.         return N.height;
55.     }
57.     // 获取平衡因子
58.     int getBalance(TreeNode N) {
59.         if (N == null)
60.             return 0;
62.         return height(N.left) - height(N.right);
63.     }
65.     // 插入节点
66.     TreeNode insert(TreeNode node, int key) {
67.         // 典型的BST插入
68.         if (node == null)
69.             return (new TreeNode(key));
71.         if (key < node.key)
72.             node.left = insert(node.left, key);
73.         else if (key > node.key)
74.             node.right = insert(node.right, key);
75.         else // 重复键
76.             return node;
78.         // 更新当前节点的高度
79.         node.height = 1 + Math.max(height(node.left), height(node.right));
81.         // 获取平衡因子
82.         int balance = getBalance(node);
84.         // 如果当前节点失衡，则进行旋转
86.         // 左左情况
87.         if (balance > 1 && key < node.left.key)
88.             return rightRotate(node);
90.         // 右右情况
91.         if (balance < -1 && key > node.right.key)
92.             return leftRotate(node);
94.         // 左右情况
95.         if (balance > 1 && key > node.left.key) {
96.             node.left = leftRotate(node.left);
97.             return rightRotate(node);
98.         }
100.         // 右左情况
101.         if (balance < -1 && key < node.right.key) {
102.             node.right = rightRotate(node.right);
103.             return leftRotate(node);
104.         }
106.         // 返回（未修改的）节点指针
107.         return node;
108.     }
110.     // 查找节点（递归）
111.     boolean search(TreeNode root, int key) {
112.         // 基本情况：空树或树中只有一个节点
113.         if (root == null || root.key == key)
114.             return root != null;
116.         // 如果键小于根节点的键，则递归地在左子树中查找
117.         if (root.key > key)
118.             return search(root.left, key);
120.         // 否则递归地在右子树中查找
121.         return search(root.right, key);
122.     }
124.     // 插入新键
125.     void insert(int key) {
126.         root = insert(root, key);
127.     }
129.     // 查找键
130.     boolean search(int key) {
131.         return search(root, key);
132.     }
134.     // 主函数（测试）
135.     public static void main(String[] args) {
136.         AVLTree tree = new AVLTree();
138.         /* 构造树
139.               50
140.            /     \
141.           30      70
142.          /  \    /  \
143.         20   40  60   80 */
144.         tree.insert(50);
145.         tree.insert(70);
146.         tree.insert(30);
147.         tree.insert(20);
148.         tree.insert(80);
149.         tree.insert(40);
150.         tree.insert(60);
152.         // 查找键
153.         System.out.println("查找 20: " + tree.search(20));
154.         System.out.println("查找 30: " + tree.search(30));
155.         System.out.println("查找 100: " + tree.search(100));
156.     }
157. }

复制代码

假设使用该结构作为数据存储结构的话，AVL如下所示

索引必须要存你创建索引的字段的值，对应关键字，好比id的值。还要存完备纪录在磁盘上的所在，对应数据区。由于AVL树是二叉树，以是还要额外地存储左右子节点的指针。

• 当我们用树的结构来存储索引的时间，访问一个节点就要跟磁盘之间发生一次 I0 操纵。InnoDB 操纵磁盘的最小的单位是一页(大概叫一个磁盘块)，巨细是16K(16384字节)，一个节点只放一个索引和数据所在，就会很浪费资源。
  
• 好比上面这张图，我们一张表内里有6条数据，当我们查询id=8的时间，要查询两个子节点，就须要跟磁盘交互3次，假设一次磁盘IO须要10ms， 6条数据就须要30ms，如果我们有上亿数据呢，当时间很很耗时。如果查询的数据是个范围，那这个时间又是成倍的增长。
  

以是如许的结构作为索引，是不太公道的。是须要去优化的。
我们把题目点列出来

• 1、节点生存的数据少，浪费资源 -> 让节点生存更多数据
  
• 2、树的深度太大，IO遍历太多 -> 节点生存的数据变多，那节点的分叉也可以变多，每个分叉后的节点又能生存数据，如许的话深度就大大镌汰
  

四、多路平衡查找树（B Tree）

B树是一种多路平衡查找树，广泛用于数据库和文件体系等须要动态排序数据结构的体系中。它以其高效的插入、删除、查找操纵而著称，特殊得当磁盘存储体系，可以有效镌汰磁盘I/O操纵次数。有一个比力显着的特点：分叉数（路数）永世比关键字数多1
B树的界说和特性

• 阶（Order）：
  B树的阶（order）是树的告急特性，通常用字母m表现。阶m表现每个节点最多有m个子节点。
  
• 节点的关键字（Keys）：
  每个节点最多可以有m-1个关键字，最少有⌈m/2⌉-1个关键字（根节点可以破例）。
  
• 节点的子节点数量（Children）：
  非叶子节点至少有⌈m/2⌉个子节点，至多有m个子节点。如果一个节点有n个关键字，则它恰恰有n+1个子节点。
  
• 排序特性：
  设x是一个节点，x中的关键字按次序分列：K1, K2, …, Kn。则对于x的子节点：C1, C2, …, Cn+1，有全部节点C1中的关键字 < K1，全部节点C2中的关键字在K1和K2之间，以此类推。
  
• 平衡性：
  B树是一种自平衡树，即从根节点到恣意一个叶子节点的路径长度都类似。
  

B树的根本操纵
1、搜索
搜索某个关键字从根节点开始：

• 在当前节点中找关键字，找到则竣事搜索。
  
• 否则，如果未到叶子节点，根据关键字的巨细找到下一层子节点继续搜索。
  

2、插入
向B树中插入关键字，需保持树的平衡性：

• 从根节点开始找到精确的叶子节点位置。
  
• 如果叶子节点未满，直接插入。
  
• 如果叶子节点已满，则举行节点分裂，将中心关键字提升到父节点。
  这大概导致父节点分裂，递归向上处理惩罚，大概导致树的高度增长。
  

3、删除
从B树中删除关键字须要分几种环境：

• 在叶子节点删除关键字：
  直接删除，如果节点关键字数少于最小值，则须要借位或归并处理惩罚。
  
• 在内部节点删除关键字：
  找到前驱或后继关键字更换之，并递归删除前驱或后继关键字，类似于二叉查找树的删除。
  采取借位或归并计谋以保持树的平衡。
  

B树的上风
Mysql为了更好的使用磁盘的预读本领，把一个Page页的巨细设置为16k，也就是一个节点（磁盘块）的巨细是16K。也就是说在举行一次磁盘IO时，会把一个节点（16K）的索引加载到内存中。假设我们设置的一个表的索引字段范例是int，也就是4个字节，如果每个关键字对应的数据区(data)也是4个字节。
在不思量子节点引用的环境下，那么在B Tree中，每个阶段大概能存储的关键字数量是：
( 16 * 1024 ) / 4+4 = 2048 个关键字
在B Tree中，一共有2049路。 对于二叉树来说，三层高度最多可以生存7个关键字，而对于这种2001路的B树，三层高度可以大概生存的关键字数远宏大于二叉树，因此B Tree用来存储索引非常符合。

五、增强版多路平衡查找树（B+ Tree）

在Mysql的InnoDB引擎中，并没有使用B Tree作为索引的存储结构，而是使用B+Tree！它的存储结构如下图所示。

B+ Tree相比B Tree，做了以下几个方面的优化：

• B树的路数和关键字的个数的关系不再建立了，数据检索规则接纳的是左闭合区间，路数和关键个数关系为1比1
  
• B+Tree的根节点和枝节点中都不会存储数据，只有叶子节点才存储数据，而且每个叶子节点都会增长一个指针指向响铃的叶子节点，形成一个有序链表结构。
  

在如许的几个B+ Tree结构下，假设我们要检索x=1的数据，那么检索的规则是：

• 取出跟磁盘块， 加载1/26/66三个关键字。
  
• x<=1， 取出磁盘块2，加载1/10/20三个关键字。
  
• x<=1， 取出叶子节点，加载1/8/9三个关键字。此时已经到达了叶子节点，掷中1， 以是只须要加载对应1的数据内容（大概内容所在）即 可！
  

B+Tree特性带来的上风：

• 它是B Tree的变种，B Tree能办理的题目，它都能办理。B Tree办理的两大题目是什么？（每个节点存储更多关键字；路数更多）
  
• 扫库、扫表本领更强（如果我们要对表举行全表扫描，只须要遍历叶子节点就可以了，不须要遍历整棵B+Tree拿到全部的数据）
  
• B+Tree的磁盘读写本领相对于B Tree来说更强（根节点和枝节点不生存数据区，以是一个节点可以生存更多的关键字，一盘加载的关键字更多）
  
• 排序本领更强（由于叶子节点上有下一个数据区的指针，数据形成了链表）
  
• 服从更加稳固（B+Tree永世是在叶子节点拿到数据，以是IO次数是稳固的）
  

由于在B+ Tree中，每个节点不存存储数据区，只须要存储键值+指针，使得 B+ Tree在每个节点存储的路数更多。
假设索引字段+指针巨细一共是16个字节，那么一个Page页（一个节点）能存储1000个如许的单位（键值+指针）。
假设一条纪录是16bytes，一个叶子节点（一页）可以存储10条纪录！
当数的深度是2的时间，就有1000^2个叶子节点，可存储的数据为1000 x 1000 x 10 =10000000（千万）
也就是说在InnoDB中B+树的深度在3层左右，就能满足千万级别的数据存储。

---

总结

架构的不绝升级带来了更多的性能提升，这点值得我们参考与提升