数据库索引入门（上）：浅谈原理
浅谈数据库索引原理
阅读本文需要的前置知识：
MySQL 数据库的CRUD使用
数据结构与算法知识：查找、二叉树、二叉搜索树、平衡二叉树
计算机组成原理：简要存储器知识
在fxiaoke实习的第一周，在公司的研发避坑手册看到了这句话：
看样子在实际开发中，不使用数据库索引是不行的，但是乱用数据库索引也是不行的。
那么，什么是数据库索引？为啥数据库索引就能加快查询速度、降低数据库负载？索引是在数据库的哪里进行执行、怎么执行的？如何衡量数据库的查询速度与负载情况？
本文：
从数据结构的查找算法开始，讲述索引的概念，如何使用索引进行查找
从最常见的索引结构B树、 B+树
从最常见的一种数据库引擎——MySQL InnoDB
出发，进行体系架构、存储引擎的简要分析，进以了解索引是什么。
1. 索引简介
其实在关系型数据库当中，我们都会进行查询操作，而查询操作的本质就是根据 WHERE 子句进行查找：
SELECT id, name FROM t_student WHERE age = 18所以我们不妨先脱离数据库这个概念，先从查找算法开始讲起，然后直观的介绍索引是个什么东西。
1.1 由查找到索引
复习一下几个常见的查找算法：（不是重点，了解即可）
顺序表查找：从线性表一端开始逐个检查 key 满足的条件。时间复杂度 O(n)
/*有哨兵顺序查找*/
int Sequential_Search(int *a, int n, int key){
int i;
a[0] = key; //设置a[0]为关键字，称之为“哨兵”
i = n; //循环从数组尾部开始
while(a[i] != key){
i--;
}
return i; //返回0则说明查找失败
}二分查找：先将线性表按 key 排序，再取中间 key 做比较。时间复杂度 O(logn)。
int Binary_Search(SeqList L, ElemType key){
int low = 0, high = L.length - 1, mid;
while(low <= high){
mid = (low + hight)/2; //取中间位置
if(L.elem[mid] == key){
return mid; //查找成功返回所在位置
}else if(L.elem[mid] > key){
high = mid - 1; //从前半部分继续查找
}else{
low = mid + 1; //从后半部分继续查找
}
}
return -1; //查找失败，返回-1
}算法时间复杂度算是降低了，but这里有几个问题：因为折半查找需要方便地定位查找区域，所以它要求线性表必须具有随机存取的特性。因此，该查找法仅适合于：
顺序存储结构，不适合于链式存储结构
要求元素按关键字有序排列。
因此我们如果要想进行二分查找，我们可以想到每次查找都将他排一次序就好了，but排序算法一般为 O(nlogn) ，平白无故加了一个算法复杂度！
于是我们想，能不能直接在中间加一层数据结构（如线性表），存放已经排序好的 key，然后每次对已经排序好的 key 进行操作呢？
稠密索引
现实生活中计算机要处理的数据量是极其庞大的，而数据结构的最终目的是提高数据的处理速度，索引是为了加快查找速度而设计的一种数据结构。索引就是把一个关键字与它对应的记录相关联的过程， 一个索引由若干个索引项构成，每个索引项至少应包含关键字和其对应的记录在存储器中的位置等信息。索引技术是组织大型数据库以及磁盘文件的一种重要技术。
索引按照结构可以分为线性索引、树形索引和多级索引。
所谓线性索引就是将索引项集合组织为线性结构，也称为索引表。三种线性索引：稠密索引、分块索引和倒排索引。
上图即为稠密索引。稠密索引是指在线性索引中，将数据集中的每个记录对应一个索引项，而索引项一定是按照关键码有序的排列。
1.2 查找算法与索引
我们可以用任意一种查找算法对某个数据结构建立索引。
比如我们有一个数据结构 Person ，以Java代码为例定义如下：
// 定义Person类
class Person {
String firstName;
String lastName;
// Java 构造方法
public Person(String firstName, String lastName) {
this.firstName = firstName;
this.lastName = lastName;
}
@Override
public String toString() {
return "Person{" +
"firstName='" + firstName + '\'' +
", lastName='" + lastName + '\'' +
'}';
}
}按照之前的思路，我们可以用一个线性表 List<Person>存储Person对象，这里我们把它省略掉，直接用 IndexExample 来管理 Person 对象；然后再我们可以用HashMap存储Person对象，就相当于使用 Hash 查找算法对其建立了一个索引：
public class IndexExample {
// 使用HashMap来为firstName建立索引
private Map<String, Person> firstNameIndex = new HashMap<>();
// 使用HashMap来为lastName建立索引
private Map<String, Person> lastNameIndex = new HashMap<>();
public void addPerson(Person person) {
// 为firstName建立索引
firstNameIndex.put(person.firstName, person);
// 为lastName建立索引
lastNameIndex.put(person.lastName, person);
}
public Person findPersonByFirstName(String firstName) {
// 使用HashMap的get方法获取
return firstNameIndex.get(firstName);
}
public Person findPersonByLastName(String lastName) {
return lastNameIndex.get(lastName);
}
}主方法测试：
public static void main(String[] args) {
IndexExample indexExample = new IndexExample();
// 创建Person对象
Person alice = new Person("Alice", "Smith");
Person bob = new Person("Bob", "Johnson");
// 添加Person对象到索引
indexExample.addPerson(alice);
indexExample.addPerson(bob);
// 根据firstName查找Person
Person foundByFirstName = indexExample.findPersonByFirstName("Alice");
if (foundByFirstName != null) {
System.out.println("Found by first name: " + foundByFirstName);
}
// 根据lastName查找Person
Person foundByLastName = indexExample.findPersonByLastName("Johnson");
if (foundByLastName != null) {
System.out.println("Found by last name: " + foundByLastName);
}
}1.3 AVL 树代码实现
在介绍下面之前，先摆一下AVL树（平衡二叉树）的代码：
// 定义AVL树节点
class AVLNode {
Person data;
AVLNode left, right;
int height;
public AVLNode(Person data) {
this.data = data;
this.height = 1;
}
}
// AVL树实现
class AVLTree {
AVLNode root;
// 计算节点的高度
private int height(AVLNode N) {
if (N == null)
return 0;
return N.height;
}
// 右旋操作
private AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
// 左旋操作
private AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
// 获取平衡因子
private int getBalance(AVLNode N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
// 插入操作
public void insert(Person data) {
root = insertRec(root, data);
}
private AVLNode insertRec(AVLNode node, Person data) {
// 标准的二叉搜索树插入过程
if (node == null)
return (new AVLNode(data));
// 树的搜索部分
if (data.firstName.compareTo(node.data.firstName) < 0)
node.left = insertRec(node.left, data);
else if (data.firstName.compareTo(node.data.firstName) > 0)
node.right = insertRec(node.right, data);
// 更新节点的高度
node.height = 1 + Math.max(height(node.left), height(node.right));
// 获取平衡因子
int balance = getBalance(node);
// 如果左子树比右子树高，进行右旋
if (balance > 1 && data.firstName.compareTo(node.left.data.firstName) < 0)
return rightRotate(node);
// 如果右子树比左子树高，进行左旋
if (balance < -1 && data.firstName.compareTo(node.right.data.firstName) > 0)
return leftRotate(node);
// 如果右子树的左子树比左子树高，先进行左旋再进行右旋
if (balance > 1 && data.firstName.compareTo(node.left.data.firstName) > 0) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
// 如果左子树的右子树比右子树高，先进行右旋再进行左旋
if (balance < -1 && data.firstName.compareTo(node.right.data.firstName) < 0) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
// 查找操作
public Person find(String firstName) {
return findRec(root, firstName);
}
private Person findRec(AVLNode node, String firstName) {
if (node == null || node.data.firstName.equals(firstName))
return node != null ? node.data : null;
if (firstName.compareTo(node.data.firstName) < 0)
return findRec(node.left, firstName);
return findRec(node.right, firstName);
}
// 其他AVL树操作，如删除等...
}1.4【关键】对不同属性建立不同的索引
我们可以实现对不同属性建立不同的索引，比如我想用Hash查找算法管理 firstName 属性，而用 AVLTree 来管理 lastName 属性，就可以创建一个 PersonIndex 类：
// 管理两种索引的类
class PersonIndex {
private Map<String, Person> firstNameIndex = new HashMap<>();
private AVLTree lastNameIndex = new AVLTree();
public void addPerson(Person person) {
firstNameIndex.put(person.firstName, person);
lastNameIndex.insertByLastName(person);
}
public Person findPersonByFirstName(String firstName) {
return firstNameIndex.get(firstName);
}
public Person findPersonByLastName(String lastName) {
return lastNameIndex.findByLastName(lastName);
}
}主方法：
// 测试类
public class Main {
public static void main(String[] args) {
PersonIndex personIndex = new PersonIndex();
// 创建Person对象
Person alice = new Person("Alice", "Smith");
Person bob = new Person("Bob", "Johnson");
// 添加Person对象到索引
personIndex.addPerson(alice);
personIndex.addPerson(bob);
// 根据firstName查找Person
Person foundByFirstName = personIndex.findPersonByFirstName("Alice");
if (foundByFirstName != null) {
System.out.println("Found by first name: " + foundByFirstName);
}
// 根据lastName查找Person
Person foundByLastName = personIndex.findPersonByLastName("Johnson");
if (foundByLastName != null) {
System.out.println("Found by last name: " + foundByLastName);
}
}
}在这个示例中，PersonIndex类管理了两种索引：firstNameIndex使用HashMap实现，而lastNameIndex使用AVLTree实现。addPerson方法将Person对象添加到这两种索引中。findPersonByFirstName和findPersonByLastName方法允许我们根据给定的firstName或lastName快速检索Person对象。
也就是说，我们可以选用合适的索引数据结构，对不同的字段进行查找，哪个更高效就可以用哪个。
因此，我们可以对一个实体类的不同属性/字段建立多个索引。而且编写以上代码这个过程能让我们更好的明白索引的几个特性（这里数据库表这个概念可以平移到Java内存数据库中）：
一、为什么要创建索引呢（优点）
创建索引可以大大提高系统的性能。
通过创建唯一性索引，可以保证数据库表中每一行数据的唯一性。
可以大大 加快数据的检索速度 ，这也是创建索引的最主要的原因。
在使用分组和排序子句进行数据检索时，同样可以显著减少查询中分组和排序的时间。
二、建立方向索引的不利因素（缺点）
创建索引和维护索引要耗费时间 ，这种时间随着数据量的增加而增加。
索引需要占物理空间 ，除了数据表占数据空间之外，每一个索引还要占一定的物理空间，如果要建立聚簇索引，那么需要的空间就会更大。
当对表中的数据进行增加、删除和修改的时候， 索引也要动态的维护 ，这样就降低了数据的维护速度。
2. B树与B+树
从树的数据结构到B树、B+树，知识点的前置顺序如下：
树的定义和属性：
树的基本概念，包括节点、边、根、叶子、深度、高度等。
二叉树：
二叉树的定义和特性。
二叉树的遍历算法（前序、中序、后序、层序遍历）。
二叉搜索树（BST）：
BST的定义和特性。
在BST中进行搜索、插入和删除操作的方法。
树的遍历和操作：
理解树的递归遍历和迭代遍历。
树的转换操作，如将普通树转换为二叉树。
平衡二叉树：
AVL树和红黑树等自平衡二叉搜索树的平衡机制和旋转操作。
多路搜索树：
B-树和B+树的定义、特性和应用场景。
B-树和B+树的插入、删除和查找操作。
2.1 二叉树与二叉搜索树BST
由 Kimi.ai 生成
二叉树的定义和特性
定义：
- 二叉树是每个节点最多有两个子节点的树结构，通常称为左子节点和右子节点。
特性：
- 没有兄弟节点：每个节点最多只能有两个子节点。
- 有序性：左子节点的值总是小于或等于父节点的值，而右子节点的值总是大于或等于父节点的值（这是二叉搜索树的特性，普通的二叉树不一定满足）。
二叉树的遍历算法
遍历二叉树是指访问树中的每个节点，按照一定的顺序。以下是几种常见的遍历方法：
1. 前序遍历（Pre-order Traversal）：
- 访问根节点。
- 遍历左子树（前序）。
- 遍历右子树（前序）。
2. 中序遍历（In-order Traversal）：
- 遍历左子树（中序）。
- 访问根节点。
- 遍历右子树（中序）。
3. 后序遍历（Post-order Traversal）：
- 遍历左子树（后序）。
- 遍历右子树（后序）。
- 访问根节点。
4. 层序遍历（Level-order Traversal）：
- 使用队列来实现，按照从上到下，从左到右的顺序访问每个节点。
二叉搜索树（BST）的定义和特性
定义：
- 二叉搜索树是一种特殊的二叉树，其中每个节点的值大于其左子树上所有节点的值，小于其右子树上所有节点的值。
特性：
- 自然排序：树的中序遍历结果是有序的。
- 搜索效率：对于平衡的BST，搜索操作的时间复杂度为O(log n)，对于不平衡的BST，最坏情况下的时间复杂度为O(n)。
在BST中进行搜索、插入和删除操作的方法
1. 搜索：
- 从根节点开始，比较目标值与当前节点的值。
- 如果目标值小于当前节点的值，转到左子节点；如果大于，转到右子节点。
- 如果找到目标值，返回节点；如果到达空节点，表示未找到。
2. 插入：
- 搜索BST以找到新节点应该插入的位置。
- 如果新节点的值小于当前节点的值，将其插入到左子树中；如果大于，插入到右子树中。
- 如果左或右子节点为空，直接插入新节点；否则，继续搜索子树。
3. 删除：
- 搜索BST以找到要删除的节点。
- 如果节点是叶子节点（没有子节点），直接删除它。
- 如果节点只有一个子节点，用其子节点替换它，然后删除子节点。
- 如果节点有两个子节点，找到其右子树中的最小值节点（或左子树中的最大值节点），用这个节点替换要删除的节点，然后删除原来的最小值或最大值节点。
平衡BST（如AVL树或红黑树）通过旋转和其他操作来保持树的平衡，确保操作的效率。
理解这些基本概念和操作是掌握二叉树和BST的关键。实际编程时，这些操作通常需要递归实现，因此熟练掌握递归逻辑是非常重要的。
2.2 平衡二叉树
平衡二叉树是一种特殊的二叉搜索树，它在进行插入和删除操作后能够自动调整树的结构，以保持树的平衡，从而确保树的高度尽可能地低，使得所有操作都能在对数时间内完成。下面是AVL树的介绍，包括它们的平衡机制和旋转操作。
定义：
AVL树是一种自平衡的二叉搜索树，由Adelson-Velsky和Landis在1962年发明。
平衡条件：
AVL树的每个节点的左子树和右子树的高度差（平衡因子）不能超过1。
旋转操作：
为了维持平衡，AVL树使用四种类型的旋转操作：
1. 右旋（Right Rotation）：
- 当节点的左子树比右子树高太多时，执行右旋。
- 将节点的左子节点提升为新的根节点，原节点变为新根的右子节点。
2. 左旋（Left Rotation）：
- 当节点的右子树比左子树高太多时，执行左旋。
- 将节点的右子节点提升为新的根节点，原节点变为新根的左子节点。
3. 左右旋（Left-Right Rotation）：
- 当节点的左子树的右子树比左子树高太多时，先对左子树执行左旋，然后对原节点执行右旋。
4. 右左旋（Right-Left Rotation）：
- 当节点的右子树的左子树比右子树高太多时，先对右子树执行右旋，然后对原节点执行左旋。
2.3 AVL树与磁盘IO的适用性问题
以上，我们讨论的数据结构操作，都是在内存中进行操作的。
but 我们都知道，一旦数据量大起来，尤其是到GB级的，那么内存里肯定是放不下的，需要持久存储到硬盘里面。
于是我们对数据的操作就多了一步：把数据从外存（硬盘）加载到内存内（即磁盘IO）。
然而，这样一来，一般而言内存访问的时间约为 50 ns，而磁盘在 10 ms 左右。速度相差了近 5 个数量级，磁盘读取时间远远超过了数据在内存中比较的时间。这说明程序大部分时间会阻塞在磁盘 IO 上，而非单纯的算法时间复杂度上。
MySQL 的数据是持久化的，意味着数据（索引+记录）是保存到磁盘上的，因为这样即使设备断电了，数据也不会丢失。
磁盘是一个慢的离谱的存储设备，有多离谱呢？
人家内存的访问速度是纳秒级别的，而磁盘访问的速度是毫秒级别的，也就是说读取同样大小的数据，磁盘中读取的速度比从内存中读取的速度要慢上万倍，甚至几十万倍。
磁盘读写的最小单位是扇区，扇区的大小只有
512B大小，操作系统一次会读写多个扇区，所以操作系统的最小读写单位是块（Block）。Linux 中的块大小为4KB，也就是一次磁盘 I/O 操作会直接读写 8 个扇区。由于数据库的索引是保存到磁盘上的，因此当我们通过索引查找某行数据的时候，就需要先从磁盘读取索引到内存，再通过索引从磁盘中找到某行数据，然后读入到内存，也就是说查询过程中会发生多次磁盘 I/O，而磁盘 I/O 次数越多，所消耗的时间也就越大。
所以，我们希望索引的数据结构能在尽可能少的磁盘的 I/O 操作中完成查询工作，因为磁盘 I/O 操作越少，所消耗的时间也就越小。
另外，MySQL 是支持范围查找的，所以索引的数据结构不仅要能高效地查询某一个记录，而且也要能高效地执行范围查找。
所以，要设计一个适合 MySQL 索引的数据结构，至少满足以下要求：
能在尽可能少的磁盘的 I/O 操作中完成查询工作；
要能高效地查询某一个记录，也要能高效地执行范围查找；
AVL 树有什么致命的问题呢？
AVL树是通过旋转来保持平衡的，而旋转是对整棵树的操作，若部分加载到内存中则无法完成旋转操作，所以AVL树的操作要全部加载加到内存中，也就是把几个GB的索引全部加载到内存中进行旋转。
树的高度越长，磁盘的IO操作越多。AVL树是二叉搜索树，高度是以2为底的
log(N)，树的高度很高。在树的搜索、插入或删除操作中，需要沿着从根节点到目标节点的路径进行访问。在基于磁盘的存储系统中，数据通常以块的形式存储。磁盘I/O操作通常以块为单位进行。即使AVL树的单个节点数据量很小，读取或写入节点数据时，也可能涉及到对整个磁盘块的读取或写入。树的高度较高意味着在进行操作时可能需要访问更多的磁盘块。两个大小相近的节点，在树的表示上可能很远。不符合存储器的局部访问原理，范围查找效率低，也没有利用到硬盘的顺序存储优势。
8和10大小相近，但是在述上离得很远；如果添加一个9，9和10相差更小但是离的更远了。
树的高度与磁盘I/O操作之间的关系主要体现在树的遍历和搜索过程中。以下是几个关键点来解释这种关系：
1. 访问路径长度：在树的搜索、插入或删除操作中，需要沿着从根节点到目标节点的路径进行访问。树的高度直接影响这个路径的长度。树的高度越低，访问路径越短，需要访问的节点就越少。
2. 磁盘块访问：在基于磁盘的存储系统中，数据通常以块的形式存储。每个节点可能对应一个或多个磁盘块。树的高度较高意味着在进行操作时可能需要访问更多的磁盘块。
3. 缓存效率：现代计算机系统使用缓存来减少对慢速磁盘的访问。如果树的高度较低，那么在树的遍历过程中，更多的节点可以被加载到缓存中，从而提高缓存命中率，减少实际的磁盘I/O操作。
4. 局部性原理：磁盘I/O操作受益于数据的局部性原理，即程序倾向于多次访问同一块数据。树的高度较低时，树的节点在内存中更紧凑，更容易利用数据的局部性原理，减少磁盘访问。
5. 顺序读取优势：磁盘通常对顺序读取操作有较好的性能。如果树的高度较低，那么在遍历树时，可以更有效地利用磁盘的顺序读取优势。
6. 减少旋转操作：在需要保持平衡的树结构（如AVL树）中，树的高度较低可以减少为保持平衡所需的旋转操作次数，从而减少因旋转操作导致的额外磁盘I/O。
7. 减少分裂和合并操作：对于B树这样的结构，较低的树高度意味着在插入和删除操作中，需要进行的节点分裂和合并操作的次数减少，这些操作通常涉及到多个磁盘块的更新。
8. 减少磁盘寻道时间：磁盘I/O操作包括寻道时间（移动磁盘头到正确的磁道）和旋转延迟（等待磁盘旋转到正确的扇区）。树的高度较低可以减少需要访问的磁盘块数量，从而减少寻道时间和旋转延迟的总体影响。
9. 减少页故障：在虚拟内存系统中，如果树的高度较低，那么在访问树时可能导致的页故障（需要从磁盘加载数据到内存）也会减少，因为更多的数据可以一次性加载到内存中。
总之，树的高度直接影响到访问树中数据所需的磁盘I/O操作的数量和效率。较低的树高度有助于减少I/O操作次数，提高性能，特别是在磁盘I/O密集型的应用中。
因此我们要找一个优化后的数据结构以适应外存数据系统，需要解决以下问题：
不要使用旋转保持平衡，不要把整个索引加载到内存
减少树的高度，每次读取磁盘块尽量读取更多的数据
两个大小相近的数据，在节点的表示上也相近。
2.4 B- 树（又称B树）
B-树,这里的 B 表示 balance(平衡的意思),B-树是一种多路自平衡的搜索树（B树是一颗多路平衡查找树）
它类似普通的平衡二叉树，不同的一点是B-树允许每个节点有更多的子节点。
下图是 B-树的简化图：
B-树有如下特点:
所有键值分布在整颗树中（索引值和具体data都在每个节点里）；
任何一个关键字出现且只出现在一个结点中；
搜索有可能在非叶子结点结束（最好情况O(1)就能找到数据）；
在关键字全集内做一次查找,性能逼近二分查找；
B-树是专门为外部存储器设计的，如磁盘，它对于读取和写入大块数据有良好的性能，所以一般被用在文件系统及数据库中。
我们从“迎合”磁盘的角度来看看B-树的设计。
索引的效率依赖与磁盘 IO 的次数，快速索引需要有效的减少磁盘 IO 次数，如何快速索引呢？索引的原理其实是不断的缩小查找范围，就如我们平时用字典查单词一样，先找首字母缩小范围，再第二个字母等等。平衡二叉树是每次将范围分割为两个区间。为了更快，B-树每次将范围分割为多个区间，区间越多，定位数据越快越精确。那么如果节点为区间范围，每个节点就较大了。所以新建节点时，直接申请页大小的空间（磁盘存储单位是按 block 分的，一般为 512 Byte。磁盘 IO 一次读取若干个 block，我们称为一页，具体大小和操作系统有关，一般为 4 k，8 k或 16 k），计算机内存分配是按页对齐的，这样就实现了一个节点只需要一次 IO。
上图是一棵简化的B-树，多叉的好处非常明显，有效的降低了B-树的高度，为底数很大的 log n，底数大小与节点的子节点数目有关，一般一棵B-树的高度在 3 层左右。层数低，每个节点区确定的范围更精确，范围缩小的速度越快（比二叉树深层次的搜索肯定快很多）。上面说了一个节点需要进行一次 IO，那么总 IO 的次数就缩减为了 log n 次。
B树的每个节点，都是存多个值的，不像二叉树那样，一个节点就一个值，B树把每个节点都给了一点的范围区间，区间更多的情况下，搜索也就更快了，比如：有1-100个数，二叉树一次只能分两个范围，0-50和51-100，而B树，分成4个范围 1-25， 25-50，51-75，76-100一次就能筛选走四分之三的数据。所以作为多叉树的B树是更快的
我们来看看B-树的查找，假设每个节点有 n 个 key值，被分割为 n+1 个区间，注意，每个 key 值紧跟着 data 域，这说明B-树的 key 和 data 是聚合在一起的。一般而言，根节点都在内存中，B-树以每个节点为一次磁盘 IO，比如上图中，若搜索 key 为 25 节点的 data，首先在根节点进行二分查找（因为 keys 有序，二分最快），判断 key 25 小于 key 50，所以定位到最左侧的节点，此时进行一次磁盘 IO，将该节点从磁盘读入内存，接着继续进行上述过程，直到找到该 key 为止。
Data* BTreeSearch(Root *node, Key key) {
Data* data;
if(root == NULL)
return NULL;
// 在已经加载到内存的 node 节点里 进行二分查找 不是性能瓶颈
data = BinarySearch(node);
if(data->key == key)
{
return data;
} else{
// 性能瓶颈：磁盘 IO 时间复杂度 底数很大的 log n
node = ReadDisk(data->next);
BTreeSearch(node, key);
}
}2.5 B+树
B+树是B-树的变体，也是一种多路搜索树, 它与 B- 树的不同之处在于:
所有关键字存储在叶子节点出现,内部节点(非叶子节点并不存储真正的 data)
为所有叶子结点增加了一个链指针，增加了区间访问性。
你会发现，除了叶子节点存数据之外，其它的节点都只存了索引，而且其他节点的索引都是可以重复出现的！
因为内节点并不存储 data，所以一般B+树的叶节点和内节点大小不同，而B-树的每个节点大小一般是相同的，为一页。
2.6 B+树与B-树的区别
固定时间复杂度
B+树内节点不存储数据，所有 data 存储在叶节点导致查询时间复杂度固定为 log n。而B-树查询时间复杂度不固定，与 key 在树中的位置有关，最好为O(1)。
如下所示B-树/B+树查询节点 key 为 50 的 data。
B-树：
从上图可以看出，key 为 50 的节点就在第一层，B-树只需要一次磁盘 IO 即可完成查找。所以说B-树的查询最好时间复杂度是 O(1)。
B+树：
由于B+树所有的 data 域都在根节点，所以查询 key 为 50的节点必须从根节点索引到叶节点，时间复杂度固定为 O(log n)。
节点联通与区间访问性
B+树叶节点两两相连可大大增加区间访问性，可使用在范围查询等，而B-树每个节点 key 和 data 在一起，则无法区间查找。
根据空间局部性原理：如果一个存储器的某个位置被访问，那么将它附近的位置也会被访问。
B+树可以很好的利用局部性原理，若我们访问节点 key为 50，则 key 为 55、60、62 的节点将来也可能被访问，我们可以利用磁盘预读原理提前将这些数据读入内存，减少了磁盘 IO 的次数。
当然B+树也能够很好的完成范围查询。比如查询 key 值在 50-70 之间的节点。
每节点更多数据 降低IO次数
B+树更适合外部存储。由于内节点无 data 域，每个节点能索引的范围更大更精确
这个很好理解，由于B-树节点内部每个 key 都带着 data 域，而B+树节点只存储 key 的副本，真实的 key 和 data 域都在叶子节点存储。前面说过磁盘是分 block 的，一次磁盘 IO 会读取若干个 block，具体和操作系统有关，那么由于磁盘 IO 数据大小是固定的，在一次 IO 中，单个元素越小，量就越大。这就意味着B+树单次磁盘 IO 的信息量大于B-树，从这点来看B+树相对B-树磁盘 IO 次数少。
从上图可以看出相同大小的区域，B-树仅有 2 个 key，而B+树有 3 个 key。
3. MySQL 体系架构
以下是官网MySQL体系构架图，我们稍微对其进行了层级划分。
由上至下可划分为：1.网络接入层 2.服务层 3.存储引擎层 4.文件系统层
3.1 网络接入层
提供了应用程序接入MySQL服务的接口。
客户端与服务端建立连接，客户端发送SQL到服务端。
3.2 服务层
管理工具与服务
系统管理和控制工具，例如备份恢复、Mysql复制、集群等。
连接池
主要负责连接管理、授权认证、安全等等。每个客户端连接都对应着服务器上的一个线程。服务器上维护了一个线程池，避免为每个连接都创建销毁一个线程。当客户端连接到MySQL服务器时，服务器对其进行认证。可以通过用户名与密码认证，也可以通过SSL证书进行认证。登录认证后，服务器还会验证客户端是否有执行某个查询的操作权限。
由于每次建立连接需要消耗很多时间，连接池的作用就是将这些连接缓存下来，下次可以直接用已经建立好的连接，提升服务器性能。
3.3 存储引擎层
负责数据的存储和读取，与数据库文件打交道。 服务器中的查询执行引擎通过API与存储引擎进行通信，通过接口屏蔽了不同存储引擎之间的差异。
MySQL采用插件式的存储引擎。MySQL为我们提供了许多存储引擎，如InnoDB，每种存储引擎有不同的特点。我们可以根据不同的业务特点，选择最适合的存储引擎。
MySQL区别于其他数据库的最重要的一个特点就是插件式的表存储引擎，注意：存储引擎是基于表的。
3.4 文件系统层
该层主要是将数据库的数据存储在文件系统之上，并完成与存储引擎的交互。
存储引擎是基于表的，以下分别使用MyISAM和InnoDB存储引擎建立两张表，看看其在文件系统中对应的文件存储格式。
存储引擎为MyISAM：
*.frm：与表相关的元数据信息都存放在frm文件，包括表结构的定义信息等
*.MYD：MyISAM DATA，用于存储MyISAM表的数据
*.MYI：MyISAM INDEX，用于存储MyISAM表的索引相关信息
存储引擎为InnoDB：
*.frm：与表相关的元数据信息都存放在frm文件，包括表结构的定义信息等
*.ibd：InnoDB DATA，表数据和索引的文件。该表的索引(B+树)的每个非叶子节点存储索引，叶子节点存储索引和索引对应的数据
常见存储引擎的区别
PS：执行一条SQL语句的全链路：
4. MySQL存储引擎分析
4.1 磁盘基本知识
扇区、块/簇、页的关系
扇区： 硬盘的最小读写单元，一般为512字节（逻辑扇区）
块/簇： 文件系统层，是操作系统与硬盘之间读写的最小单元，一般为4 KB
页： 存储引擎层，是操作系统与内存之间操作的最小单元。如InnoDB为16 KB
扇区 <= 块/簇 <= 页
PS C:\Users\Donnie> fsutil fsinfo ntfsinfo E:
每扇区字节数 ： 512
每物理扇区字节数 ： 4096
每群集字节数 ： 4096 (4 KB)物理扇区是硬盘底层硬件意义上的扇区，是实际执行读写操作的最小单元。
4.2 InnoDB B+树索引简介
InnoDB使用B+Tree数据结构存储索引，根据索引物理结构可将索引划分为聚簇索引和非聚簇索引（也可称辅助索引或二级索引）。一个表中只能存在一个聚簇索引（主键索引），但可以存在多个非聚簇索引。
B+树 叶子节点包含数据表中行记录就是聚簇索引（索引和数据是一块的）。
B+树 叶子节点没包含数据表中行记录就是非聚簇索引（索引和数据是分开的）。
4.3 如何使用页进行B+树存储
每个页大小为16KB，页是InnoDB磁盘管理的最小单位，整页整页的读取。
InnoDB中主要的页类型：
数据页（BTreeNode）
Undo页（undo Log page）
系统页（System page）
事务数据页（Transaction SystemPage）
0-38：页头占据38位字节，页面id（32位的整数），页面类型，以及两个分别指向前一个page和后一个page的指针（page是一个双向列表）等信息
38-16376：不同的类型页所含的数据不同，这部分空间包含系统记录（SystemRecord）和用户记录（UserRecord），我们表中的一条条记录就放在UserRecord部分
16376-16384：页面结束标识
由页组成的链表，页之间是双向列表，页里面的数据是单向链表，这种结构组成了主键索引B+树，组成了叶子节点数据。
4.4 定位一条表记录的过程
select * from user where id = 29这里id是主键,我们通过这棵B+树来查找，首先找到根页，你怎么知道user表的根页在哪呢？
其实每张表的根页位置在表空间文件（*.frm文件）中是固定的。系统经过解析sql语句，首先
找到user表的根页面（一个表通常需要多个页面组成，跟页面就是起始页）
层级遍历非叶子节点页（索引）
读取到key值为29的指针（遍历非叶子节点的过程随着节点的遍历会将一个或多个页加载到内存）
最后到指针指向的叶子节点所在的页中，然后遍历找出该条记录。
如果使用了二级索引则先读取二级索引page遍历这个二级索引，找到装有主键信息叶子节点page页，遍历找到该主键。然后再根据主键索引寻找到该条记录。
最后的一点补充
MongoDB用的是B+树！
参考
MySQL体系构架、存储引擎和索引结构 https://blog.csdn.net/wangfeijiu/article/details/112454405
数据结构：查找(Search)【详解】 https://blog.csdn.net/Real_Fool_/article/details/114359564
一文彻底搞懂MySQL基础：B树和B+树的区别 https://blog.csdn.net/a519640026/article/details/106940115
