마지막으로 MySQL 인덱스는 B+트리를 사용해야 한다는 점과 속도가 매우 빠르다는 점을 이해했습니다.

mysql tutorial 칼럼에서는 인덱스 이해를 위한 B+트리를 소개합니다.

무료 추천: mysql 튜토리얼(동영상)

Foreword

느린 SQL을 발견하고 최적화해야 하는 경우 즉시 수행해야 합니다 어떤 최적화 방법을 생각할 수 있나요? SQL 需要进行优化时，你第一时间能想到的优化手段是什么？

大部分人第一反应可能都是添加索引，在大多数情况下面，索引能够将一条 SQL 语句的查询效率提高几个数量级。

索引的本质：用于快速查找记录的一种数据结构。

索引的常用数据结构：

1. 二叉树
2. 红黑树
3. Hash 表
4. B-tree （B树，并不叫什么B减树）
5. B+tree

数据结构图形化网址：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

索引查询

大家知道 select * from t where col = 88 这么一条 SQL 语句如果不走索引进行查找的话，正常地查就是全表扫描：从表的第一行记录开始逐行找，把每一行的 col 字段的值和 88 进行对比，这明显效率是很低的。

而如果走索引的话，查询的流程就完全不一样了（假设现在用一棵平衡二叉树数据结构存储我们的索引列）

此时该二叉树的存储结构（Key - Value）：Key 就是索引字段的数据，Value 就是索引所在行的磁盘文件地址。

当最后找到了 88 的时候，就可以把它的 Value 对应的磁盘文件地址拿出来，然后就直接去磁盘上去找这一行的数据，这时候的速度就会比全表扫描要快很多。

但实际上 MySQL 底层并没有用二叉树来存储索引数据，是用的 B+tree（B+树）。

为什么不采用二叉树

假设此时用普通二叉树记录 id 索引列，我们在每插入一行记录的同时还要维护二叉树索引字段。

此时当我要找 id = 7 的那条数据时，它的查找过程如下：

此时找 id = 7 这一行记录时找了 7 次，和我们全表扫描也没什么很大区别。显而易见，二叉树对于这种依次递增的数据列其实是不适合作为索引的数据结构。

为什么不采用 Hash 表

Hash 表：一个快速搜索的数据结构，搜索的时间复杂度 O(1)

Hash 函数：将一个任意类型的 key，可以转换成一个 int 类型的下标

假设此时用 Hash 表记录 id 索引列，我们在每插入一行记录的同时还要维护 Hash 表索引字段。

这时候开始查找 id = 7 的树节点仅找了 1 次，效率非常高了。

但 MySQL대부분의 사람들의 첫 번째 반응은 색인을 추가하는 것일 것입니다. 대부분의 경우 index는 SQL 문의 쿼리 효율성을 배수 향상시킬 수 있습니다.

색인의

본질

: 레코드를 빠르게 찾는 데 사용되는

데이터 구조

.

인덱스에 일반적으로 사용되는

데이터 구조🎜: 🎜

1. 이진 트리
2. 레드-블랙 트리
3. 해시 테이블
4. B-트리 (B-트리는 B-감산 트리라고 하지 않음)
5. B+트리

🎜🎜그래픽 데이터 구조🎜 웹사이트: https://www.cs.usfca.edu/~galles/visualization/Algorithms.html🎜

색인 쿼리🎜🎜누구나 알고 있습니다select * from t where col = 88 인덱스를 사용하지 않고 이러한 SQL 문을 검색하는 경우 일반적인 검색은 🎜전체 테이블 스캔🎜입니다. 즉, 테이블의 첫 번째 행부터 시작하여 행 단위로 검색하고, 각 행의 col 필드 값을 🎜88🎜로 검색하면 매우 비효율적입니다. 🎜🎜🎜🎜인덱스를 사용하는 경우 쿼리 프로세스는 완전히 다릅니다(🎜균형 이진 트리🎜데이터 구조가 인덱스 열을 저장하는 데 사용된다고 가정)🎜🎜이것은 바이너리 트리의 저장 구조(Key - Value): Key는 인덱스 필드의 데이터이고, Value는 인덱스가 위치한 행의 디스크 파일 주소입니다. 🎜🎜마침내 🎜88🎜을 찾으면 해당 값에 해당하는 디스크 파일 주소를 꺼낸 다음 디스크로 직접 이동하여 이 데이터 행을 찾을 수 있습니다. 이때 속도는 전체 테이블보다 빠릅니다. 많이 스캔하세요. 🎜🎜🎜🎜하지만 🎜실제로는🎜 MySQL은 하위 레이어에 인덱스 데이터를 저장하기 위해 🎜바이너리 트리🎜를 사용하지 않고 🎜B+트리를 사용합니다) 🎜. 🎜

이진 트리를 사용하면 안 되는 이유 🎜🎜 id 인덱스 열을 기록하는 데 일반 이진 트리가 사용된다고 가정합니다. 레코드 필드를 삽입하는 동안 색인을 생성합니다. 🎜🎜🎜🎜id = 7인 데이터를 찾으려는 경우 검색 과정은 다음과 같습니다. 🎜🎜🎜🎜 이때 행 레코드 id = 7 🎜7🎜번을 검색했는데 이는 전체 테이블 스캔과 크게 다르지 않습니다. 분명히 이진 트리는 실제로 🎜점점 🎜데이터 열의 종류에 대한 인덱스 데이터 구조로 🎜적합하지 않습니다 🎜. 🎜

해시 테이블을 사용하지 않는 이유🎜🎜🎜해시 테이블: 빠른 검색 데이터 구조, 검색 시간 복잡도는 O(1)🎜🎜해시 기능: 임의 유형의 키를 변환할 수 있음 int 유형 첨자로 변환됩니다. 🎜

🎜 해시 테이블이 id 인덱스 열을 기록하는 데 사용된다고 가정하면 레코드 행을 삽입하는 동안 해시 테이블 인덱스 필드를 유지해야 합니다. 🎜🎜🎜🎜이때 id = 7인 트리 노드는 🎜1🎜회만 검색되었는데, 이는 매우 효율적입니다. 🎜🎜🎜🎜그러나 MySQL의 인덱스는 여전히 🎜정확한 위치 지정이 가능한 🎜해시 테이블🎜을 사용하지 않습니다. 🎜 범위 검색어 🎜에는 🎜적용되지 않기 때문입니다 🎜. 🎜🎜레드-블랙 트리를 사용하면 안 되는 이유🎜🎜🎜레드-블랙 트리는 특수한 AVL 트리(균형 이진 트리)로 삽입 및 삭제 작업 중에 이진 검색 트리의 균형을 유지하기 위해 특정 작업을 사용합니다. 이진 탐색 트리는 레드-블랙 트리이고, 하위 트리 중 하나라도 레드-블랙 트리여야 합니다. 🎜

이때 id 인덱스 컬럼이 레드-블랙 트리를 사용하여 기록된다고 가정하면, 레코드 행을 삽입하는 동안 레드-블랙 트리 인덱스 필드를 유지해야 합니다. id 索引列，我们在每插入一行记录的同时还要维护红黑树索引字段。

插入过程中会发现它与普通二叉树不同的是当一棵树的左右子树高度差 > 1 时，它会进行自旋操作，保持树的平衡。

这时候开始查找 id = 7 的树节点只找了 3 次，比所谓的普通二叉树还是要更快的。

但 MySQL 的索引依然不采用能够精确定位和范围查询都优秀的红黑树。

因为当 MySQL 数据量很大的时候，索引的体积也会很大，可能内存放不下，所以需要从磁盘上进行相关读写，如果树的层级太高，则读写磁盘的次数（I/O交互）就会越多，性能就会越差。

B-tree

红黑树目前的唯一不足点就是树的高度不可控，所以现在我们的切入点就是树的高度。

目前一个节点是只分配了一个存储 1 个元素，如果要控制高度，我们就可以把一个节点分配的空间更大一点，让它横向存储多个元素，这个时候高度就可控了。这么个改造过程，就变成了 B-tree。

B-tree 是一颗绝对平衡的多路树。它的结构中还有两个概念

度（Degree）：一个节点拥有的子节点（子树）的数量。（有的地方是以度来说明 B-tree 的，这里解释一下）

阶（order）：一个节点的子节点的最大个数。（通常用 m 表示）

关键字：数据索引。

一棵 m 阶 B-tree

1. 삽입 과정에서 트리의 왼쪽과 오른쪽 하위 트리의 높이 차이가 1보다 크다는 점에서 일반 이진 트리와 다르다는 것을 알 수 있습니다. 회전작동하여 나무의 균형을 유지합니다.

   이때 id = 7인 트리 노드는 3회만 검색되었는데, 이는 소위 일반 이진 트리보다 여전히 빠릅니다. $$MySQL의 인덱스는 여전히 정확성이 뛰어난 빨간색과 검정색을 사용하지 않습니다. 위치 지정 및 범위 쿼리 트리. MySQL의 데이터 양이 많으면 인덱스 크기도 매우 커져 메모리에 저장되지 않을 수 있으므로 관련 읽기 및 쓰기는 디스크에서 수행해야 합니다. 트리 수준이 너무 높으면 디스크에 읽고 쓰는 횟수(I/O 상호 작용)가 많을수록 성능이 저하됩니다.

   B-트리

   레드-블랙 트리의 유일한 단점은 트리의 높이를 제어할 수 없다는 점이므로 이제 항목을 입력합니다. point나무의 높이입니다. 현재 노드는 1개의 요소만 저장하도록 할당되어 있습니다. 높이를 제어하려면 노드에 더 큰 공간을 할당하고 이때 여러 요소를 수평으로 저장하도록 할 수 있습니다. 높이 조절이 가능합니다. 이러한 변형 과정을 거쳐 B-tree가 되었습니다. B-트리는 완전히 균형 잡힌 다방향 트리입니다. 구조에는 두 가지 개념도 있습니다

   정도: 노드가 갖는 하위 노드(하위 트리)의 수입니다. (어떤 곳에서는 B-tree가 정도로 설명되는데 여기서 설명하세요.)

   Order: 노드의 최대 하위 노드 수입니다. (보통 m으로 표시) 키워드: 데이터 인덱스.
   🎜🎜🎜 🎜🎜🎜m 🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜🎜⌉🎜🎜🎜🎜🎜 하위 노드;

   $lceil dfrac{m}{2}rceil$ 2

2. $m{\displaystyle \frac{}{\mathrm{}}}$

   B-tree 찾기 검색은 실제로 이진 트리와 매우 유사합니다. 이진 트리에는 하나의 키워드와 각각 두 개의 분기가 있습니다. node , B-tree의 각 노드에는 k개의 키워드와 (k + 1)개의 분기가 있습니다. 이진 트리 검색은 왼쪽 또는 오른쪽으로 갈지 여부만 고려하는 반면 B-트리는 여러 분기에 의해 결정되어야 합니다. B-tree 검색은 두 단계로 구분됩니다.
   1. 먼저 노드를 찾으세요. B-tree는 일반적으로 디스크에 저장되므로 이 단계에서는 디스크 IO 작업이 필요합니다.
   B-tree 通常是在磁盘上存储的所以这步需要进行磁盘IO操作；

3. 查找关键字，当找到某个节点后将该节点读入内存中然后通过顺序或者折半查找来查找关键字。若没有找到关键字，则需要判断大小来找到合适的分支继续查找。

操作流程

现在需要查找元素：88

第一次：磁盘IO

第二次：磁盘IO

第三次：磁盘IO

然后这有一次内存比对，分别跟 70 与 88 比对，最后找到 88。

从查找过程中发现，B-tree 比对次数和磁盘IO的次数其实和二叉树相差不了多少，这么看来并没有什么优势。

但是仔细一看会发现，比对是在内存中完成中，不涉及到磁盘IO，耗时可以忽略不计。

另外 B-tree 中一个节点中可以存放很多的关键字（个数由阶决定），相同数量的关键字在 B-tree 中生成的节点要远远少于二叉树中的节点，相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后，性能的差异就显现出来了。

插入

当 B-tree 要进行插入关键字时，都是直接找到叶子节点进行操作。

1. 根据要插入的关键字查找到待插入的叶子节点；
2. 因为一个节点的子节点的最大个数（阶）为 m，所以需要判断当前节点关键字的个数是否小于 (m - 1)。
   • 是：直接插入
   • 否：发生节点分裂，以节点的中间的关键字将该节点分为左右两部分，中间的关键字放到父节点中即可。

操作流程

比如我们现在需要在 Max Degree（阶）为 3 的 B-tree 插入元素：72

1. 查找待插入的叶子节点

   

2. 节点分裂：本来应该和 [70,88] 在同一个磁盘块上，但是当一个节点有 3 个关键字的时候，它就有可能有 4 个子节点，就超过了我们所定义限制的最大度数 3，所以此时必须进行分裂：以中间关键字为界将节点一分为二，产生一个新节点，并把中间关键字上移到父节点中。

Tip : 当中间关键字有两个时，通常将左关键字进行上移分裂。

删除

删除操作就会比查找和插入要麻烦一些，因为要被删除的关键字可能在叶子节点上，也可能不在，而且删除后还可能导致 B-tree다음 이후에 키워드를 찾으세요. 노드를 찾고, 노드를 메모리로 읽어온 다음 순차 또는 이진 검색을 통해 키워드를 찾습니다. 키워드가 발견되지 않으면 크기를 판단하여 적합한 지점을 찾아야 검색을 계속할 수 있습니다.

작업 프로세스

이제 요소를 찾아야 합니다: 88

처음: 디스크 IO🎜🎜🎜 🎜두 번째: 디스크 IO🎜🎜🎜🎜세 번째: 디스크 IO🎜🎜그런 다음 메모리 비교가 있는데 각각 70과 88을 비교하여 최종적으로 88을 찾습니다. 🎜🎜🎜🎜검색 과정에서 B-tree의 비교 횟수와 디스크 IO 횟수는 실제로 바이너리 트리와 크게 다르지 않다는 사실을 발견했습니다. 딱히 메리트는 없는 것 같습니다. 🎜🎜하지만 자세히 살펴보면 비교가 메모리에서 완료되고 디스크 IO가 포함되지 않으며 시간 소모가 미미하다는 것을 알 수 있습니다. 🎜🎜또한 B-tree의 노드는 많은 키워드(수는 순서에 따라 결정됨)와 동일한 수의 키워드를 저장할 수 있습니다. Strong> B-tree에서 생성된 노드는 바이너리 트리의 노드보다 훨씬 적으며, 노드 수의 차이는 디스크 IO 수와 동일합니다. 특정 수치에 도달하면 성능 차이가 확연해집니다. 🎜

삽입

🎜B-tree가 키워드를 삽입하려고 할 때 리프 노드를 직접 찾아서 작업을 수행합니다. 🎜🎜🎜삽입할 키워드에 따라 삽입할 리프 노드를 찾으세요.🎜한 노드의 자식 노드의 최대 개수(순서)가 m개이므로 결정해야 합니다. 현재 노드 키워드의 수가 (m - 1)보다 작은지 여부.

🎜Yes: 직접 삽입🎜No: 노드 분할이 발생합니다. 노드의 중간 키워드를 기준으로 노드를 왼쪽과 오른쪽으로 나누어 중간 키워드를 배치합니다. 상위 노드에서 그냥 누르세요.

작업 프로세스

🎜예를 들어 이제 B-tree 요소 삽입: 72🎜🎜🎜🎜삽입할 리프 노드를 찾습니다🎜🎜🎜🎜🎜노드 분할: 디스크 블록에서 [70,88]과 동일한 위치이지만 노드에 3개의 키워드가 있는 경우 4개의 하위 노드가 있을 수 있으며 이는 우리가 정의한 제한의 최대 차수 3을 초과하므로 split은 반드시 >: 중간 키워드를 경계로 노드를 둘로 나누고, 새로운 노드를 생성한 후, 중간 키워드를 상위 노드로 이동시킵니다. 🎜🎜🎜🎜팁: 중간 키워드가 2개 있는 경우 일반적으로 왼쪽 키워드가 위로 이동합니다. 나뉘다. 🎜

삭제

🎜삭제할 키워드가 리프 노드에 있을 수도 있고 없을 수도 있고, 삭제 작업이 검색이나 삽입보다 더 번거롭기 때문입니다. 결국 B-tree의 불균형을 초래할 수도 있으며, 전체 트리의 균형을 유지하기 위해서는 병합, 회전 등의 작업이 필요합니다. 🎜🎜나무(레벨 5)를 예로 들어보세요 🎜

위 내용은 마지막으로 MySQL 인덱스는 B+트리를 사용해야 한다는 점과 속도가 매우 빠르다는 점을 이해했습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!