MySQL의 인덱스란 무엇입니까? 인덱스 저장 모델의 간략한 분석

다음 mysql 튜토리얼 칼럼에서는 MySQL의 인덱스에 대한 심층적인 분석을 제공하고 MySQL 인덱스에 대한 지식을 소개하는 것이 도움이 되기를 바랍니다.

MySQL 데이터베이스는 가장 일반적으로 사용되는 데이터베이스 중 하나여야 합니다. 이는 다양한 대기업과 중소기업에서 볼 수 있습니다. 일꾼이 일을 잘하려면 먼저 도구를 갈고 닦아야 한다는 속담처럼, 더 잘 사용하려면 먼저 그것을 이해해야 합니다. 이 기사에서는 MySQL 인덱스에 대한 일부 지식을 심층적으로 분석할 것입니다. 먼저 인덱스가 무엇인지, 그리고 기본 데이터 구조가

B+ 트리

로 선택된 이유를 살펴보겠습니다. ? 인덱스란 무엇인가요?

테이블에 5백만 개의 데이터가 있습니다. 인덱스 없이 이름 필드에 where 쿼리를 실행합니다.

select * from user_innodb where name ='小马';

이름 필드에 인덱스가 있으면 어떻게 될까요? 이름 필드에 인덱스를 생성하고 동일한 쿼리를 다시 실행합니다.

ALTER TABLE user_innodb DROP INDEX idx_name; 
ALTER TABLE user_innodb ADD INDEX idx_name (name);

인덱스가 없는 쿼리와 비교할 때 인덱스가 있는 쿼리의 효율성은 수십 배 다릅니다.

이런 경우를 통해 인덱싱이 데이터 검색 성능을 크게 향상시킬 수 있다는 것을 직관적으로 느낄 수 있을 것입니다.

그럼 인덱스란 정확히 무엇인가요? 이것이 쿼리에 그렇게 큰 영향을 미칠 수 있는 이유는 무엇입니까? 인덱스가 생성되면 어떻게 되나요?

인덱스 정의

데이터베이스 인덱스는 데이터베이스 테이블의 데이터를 빠르게 쿼리하고 업데이트하는 데 도움이 되는 데이터베이스 관리 시스템(DBMS)의 정렬된 데이터 구조입니다.

데이터는 파일 형태로 디스크에 저장되며, 각 데이터 행에는 디스크 주소가 있습니다. 인덱스가 없으면 500만 행의 데이터에서 데이터 조각을 검색해야 하며, 이 데이터 조각을 찾을 때까지 이 테이블의 모든 데이터를 순회할 수만 있습니다.

하지만 인덱스를 얻은 후에는 인덱스에서 이 데이터만 검색하면 됩니다. 왜냐하면 이는 빠른 검색을 위해 설계된 특별한 데이터 구조이기 때문입니다. 데이터가 저장된 디스크 주소를 찾은 후 이를 얻을 수 있습니다. 데이터.

인덱스 유형

InnoDB에는 일반 인덱스, 고유 인덱스(기본 키 인덱스는 특수 고유 인덱스), 전체 텍스트 인덱스의 세 가지 인덱스 유형이 있습니다.

Normal

: Non-Unique Index라고도 하며, 아무런 제한이 없는 가장 일반적인 인덱스입니다.

Unique

: 고유 인덱스를 사용하려면 키 값이 반복될 수 없어야 합니다. 또한 기본 키 인덱스는 특별한 고유 인덱스이며 키 값을 비워 둘 수 없다는 추가 제한 사항도 있습니다. 기본 키 인덱스는 기본 키를 사용하여 생성됩니다.

Fulltext

: 예를 들어 메시지 내용과 수 KB의 데이터를 저장할 때 상대적으로 큰 데이터의 경우 쿼리 효율성과 같이 낮은 문제를 해결하려면 전체 텍스트 인덱스를 만들 수 있습니다. 전체 텍스트 인덱스는 char, varchar 및 text와 같은 텍스트 유형 필드에 대해서만 생성할 수 있습니다.

인덱스는 데이터 구조인데 효율적인 데이터 검색을 위해서는 어떤 데이터 구조를 선택해야 할까요?

색인 저장 모델 추론

이진 검색

Double Eleven이 끝난 후 여자친구가 당신과 추측 게임을 했습니다. 어제 내가 얼마에 샀는지 맞춰보고 다섯 번의 기회를 주세요.

10000? 낮은. 30000? 높은. 다음에는 무엇을 추측하시겠습니까? 20000. 왜 11,000이나 29,000을 추측하지 않았나요?

이것은 절반 검색이라고도 불리는 이진 검색 아이디어입니다. 매번 후보 데이터를 절반으로 줄입니다. 이 방법은 데이터가 정렬된 경우 더 효율적입니다.

먼저 순서 배열을 인덱스 데이터 구조로 사용하는 것을 고려해 볼 수 있습니다.

동등 쿼리와 정렬된 배열의 비교 쿼리는 매우 효율적이지만, 데이터를 업데이트할 때 많은 양의 데이터를 이동(인덱스 변경)해야 할 수 있으므로 정적 데이터를 저장하는 데에만 적합합니다.

데이터 삽입 등 빈번한 수정을 지원하려면 연결 목록을 사용해야 합니다. 연결리스트의 경우, 단일 연결리스트라면 검색 효율성이 아직 충분히 높지 않습니다.

그렇다면 이진 검색을 사용할 수 있는 연결 리스트가 있나요?

이 문제를 해결하기 위해 우리가 이진 검색 트리라고 부르는 BST(Binary [ˈbaənəri] Search Tree)가 탄생했습니다.

이진 검색 트리(Binary Search Tree)

왼쪽 하위 트리의 모든 노드는 상위 노드보다 작고, 오른쪽 하위 트리의 모든 노드는 상위 노드보다 큽니다. 평면에 투영된 후에는 정돈된 선형 테이블이 됩니다.

二叉查找树既能够实现快速查找，又能够实现快速插入。

但是二叉查找树有一个问题：查找耗时是和这棵树的深度相关的，在最坏的情况下时间复杂度会退化成 O(n)。

什么情况是最坏的情况呢？

还是刚才的这一批数字，如果我们插入的数据刚好是有序的，2、10、12、15、 21、28

这个时候 BST 会变成链表（ “斜树”），这种情况下不能达到加快检索速度的目的，和顺序查找效率是没有区别的。

造成它倾斜的原因是什么呢？

因为左右子树深度差太大，这棵树的左子树根本没有节点——也就是它不够平衡。

所以，我们有没有左右子树深度相差不是那么大，更加平衡的树呢？

这个就是平衡二叉树，叫做 Balanced binary search trees，或者 AVL 树。

平衡二叉树（AVL Tree）

平衡二叉树的定义：左右子树深度差绝对值不能超过 1。

是什么意思呢？比如左子树的深度是 2，右子树的深度只能是 1 或者 3。

这个时候我们再按顺序插入 1、2、3、4、5、6，一定是这样，不会变成一棵“斜树”。

那 AVL 树的平衡是怎么做到的呢？怎么保证左右子树的深度差不能超过 1 呢？ 例如：插入 1、2、3。

当我们插入了 1、2 之后，如果按照二叉查找树的定义，3 肯定是要在 2 的右边的，这个时候根节点 1 的右节点深度会变成 2，但是左节点的深度是 0，因为它没有子节点，所以就会违反平衡二叉树的定义。

那应该怎么办呢？因为它是右节点下面接一个右节点，右-右型，所以这个时候我们要把 2 提上去，这个操作叫做左旋。

同样的，如果我们插入 7、6、5，这个时候会变成左左型，就会发生右旋操作，把 6 提上去。

所以为了保持平衡，AVL 树在插入和更新数据的时候执行了一系列的计算和调整的操作。

平衡的问题我们解决了，那么平衡二叉树作为索引怎么查询数据？ 在平衡二叉树中，一个节点，它的大小是一个固定的单位，作为索引应该存储什么内容？

第一个：索引的键值。比如我们在 id 上面创建了一个索引，我在用 where id =1 的条件查询的时候就会找到索引里面的 id 的这个键值。

第二个：数据的磁盘地址，因为索引的作用就是去查找数据的存放的地址。

第三个因为是二叉树，它必须还要有左子节点和右子节点的引用，这样我们才能找到下一个节点。比如大于 26 的时候，走右边，到下一个树的节点，继续判断。

如果是这样存储数据的话，我们来看一下会有什么问题。

首先，索引的数据，是放在硬盘上的。查看数据和索引的大小：

select CONCAT(ROUND(SUM(DATA_LENGTH/1024/1024),2),'MB') AS data_len, 
CONCAT(ROUND(SUM(INDEX_LENGTH/1024/1024),2),'MB') as index_len 
from information_schema.TABLES 
where table_schema='gupao' and table_name='user_innodb';

当我们用树的结构来存储索引的时候，因为拿到一块数据就要在 Server 层比较是不是需要的数据，如果不是的话就要再读一次磁盘。访问一个节点就要跟磁盘之间发生一次 IO。InnoDB 操作磁盘的最小的单位是一页（或者叫一个磁盘块），大小是 16K(16384 字节)。

그렇다면 트리 노드의 크기는 16K입니다. 정수 필드와 같이 노드에 하나의 키 값 + 데이터 + 참조만 저장하면 수십 또는 수십 바이트만 사용할 수 있어 16K 용량과는 거리가 멀기 때문에 트리 노드에 액세스할 때 수행할 수 있습니다. IO가 발생하면 많은 공간이 낭비됩니다.

따라서 각 노드에 너무 적은 데이터가 저장되어 있으면 인덱스에서 필요한 데이터를 찾으려면 더 많은 노드에 액세스해야 하며, 이는 디스크와의 상호 작용이 너무 많다는 것을 의미합니다.

기계식 하드 디스크 시대에는 매번 디스크에서 데이터를 읽는 데 약 10ms의 탐색 시간이 소요되며 상호 작용이 많을수록 더 많은 시간이 소요됩니다.

예를 들어, 위 그림에는 테이블에 6개의 데이터가 있습니다. id=37을 쿼리할 때 두 개의 하위 노드를 쿼리하려면 수백만 개의 데이터가 있으면 디스크와 3번 상호 작용해야 합니다. ? 이번에는 추정하기가 훨씬 더 어렵습니다.

그렇다면 우리의 솔루션은 무엇인가요?

첫 번째는 각 노드에 더 많은 데이터를 저장할 수 있도록 하는 것입니다.

둘째, 노드에 더 많은 키워드가 있을수록 더 많은 포인터를 갖게 되며, 이는 더 많은 포크가 있을 수 있음을 의미합니다.

가지가 많을수록 트리의 깊이가 감소합니다(루트 노드는 0입니다). 이렇게 되면 우리의 나무들도 원래의 키가 크고 마른 모습에서 짧고 통통한 모습으로 변화하게 될까요?

이제 우리 트리는 더 이상 두 갈래의 트리가 아니라 멀티 포크, 즉 멀티 웨이입니다.

다방향 균형 검색 트리(B 트리)

AVL 트리와 마찬가지로 B 트리는 분기 노드와 리프 노드에 키 값, 데이터 주소, 노드 참조를 저장합니다.

특징이 있습니다: 분기 수(경로 수)가 항상 키워드 수보다 1개 더 많습니다. 예를 들어, 우리가 그린 트리에서 각 노드는 두 개의 키워드를 저장하므로 세 개의 하위 노드를 가리키는 세 개의 포인터가 있습니다.

B트리 검색규칙은 어떻게 되나요?

예를 들어 이 테이블에서 15를 찾으려고 합니다. 15는 17보다 작으므로 왼쪽으로 가세요. 15는 12보다 크므로 오른쪽으로 이동합니다. 15는 디스크 블록 7에서 발견되었으며 3개의 IO만 사용되었습니다.

이것이 AVL 트리보다 더 효율적인가요? 그렇다면 B 트리는 하나의 노드가 여러 키워드를 저장하고 여전히 균형을 유지한다는 것을 어떻게 인식합니까? AVL 트리와의 차이점은 무엇입니까?

예를 들어 Max Degree(방법 수)가 3인 경우 데이터 1, 2, 3을 삽입합니다. 3을 삽입할 때는 첫 번째 디스크 블록에 있어야 하지만 노드에 3개의 키워드가 있는 경우 이 이는 4개의 포인터가 있고 하위 노드가 4방향이 되므로 이때 분할을 수행해야 함을 의미합니다(실제로는 B+Tree). 중간 데이터 2를 가져와서 1과 3을 2의 하위 노드로 바꿉니다.

노드를 삭제하면 역병합 작업이 진행됩니다.

이것은 분할 및 병합이며 AVL 트리의 왼쪽 및 오른쪽 회전과 다릅니다.

계속해서 4와 5를 삽입하면 B Tree가 다시 분할되고 병합됩니다.

이로부터 인덱스를 업데이트할 때 인덱스에 많은 구조적 조정이 있을 것임을 알 수 있습니다. 이는 자주 업데이트되는 열에 인덱스를 구축하지 않는 이유 또는 인덱스를 업데이트하지 않는 이유를 설명합니다. 기본 키.

노드 분할 및 병합은 실제로 InnoDB 페이지 분할 및 병합입니다.

B+Tree(B Tree의 향상된 버전)

B Tree는 이미 매우 효율적입니다. MySQL이 여전히 B Tree를 개선하고 마침내 B+Tree를 사용해야 하는 이유는 무엇입니까?

일반적으로 이 향상된 B-Tree 버전은 B-Tree보다 더 포괄적인 문제를 해결합니다.

InnoDB에서 B+ 트리의 저장 구조를 살펴보겠습니다.

MySQL의 B+트리에는 여러 가지 특징이 있습니다.

1. 키워드 수는 경로 수와 같습니다. ;

2. B+Tree는 루트 노드나 분기 노드에 데이터를 저장하지 않고 리프 노드에만 데이터를 저장합니다. 키워드를 검색하면 바로 반환되지 않고 마지막 레이어의 리프 노드로 이동합니다. 예를 들어 id=28을 검색하면 첫 번째 레이어에 바로 히트되지만 모든 데이터가 리프 노드에 있기 때문에 계속 아래쪽으로 리프 노드까지 검색하게 됩니다.

3. B+Tree의 각 리프 노드는 인접한 리프 노드에 포인터를 추가하고, 마지막 데이터는 다음 리프 노드의 첫 번째 데이터를 가리키며 정렬된 연결 목록 구조를 형성합니다.

4. 왼쪽-닫힘-오른쪽-열림 간격 [ )을 기준으로 데이터를 검색합니다.

B+Tree의 데이터 검색 과정:

1. 예를 들어 28을 검색하려는 경우 루트 노드에서 키 값을 찾았지만 페이지 하위 노드가 아니기 때문에 계속해서 아래쪽으로 검색하게 되는 것은 왼쪽의 임계 값입니다. -닫힘 및 오른쪽 열림 간격 [28,66)이므로 중간 자식 노드로 이동한 다음 왼쪽 닫힘, 오른쪽 열림 간격 [28,34]의 임계값인 검색을 계속합니다. ), 따라서 왼쪽 자식 노드로 이동하여 마지막으로 리프 노드에서 필요한 데이터를 찾습니다.

2. 두 번째, 범위 쿼리인 경우, 예를 들어 22부터 60까지의 데이터를 쿼리하려는 경우 22를 찾은 후 노드와 포인터를 따라 순차적으로 탐색하기만 하면 모든 데이터 노드에 한 번에 액세스할 수 있습니다. , 따라서 간격 쿼리의 효율성이 크게 향상됩니다(검색을 반복적으로 통과하기 위해 상위 상위 노드로 돌아갈 필요가 없음).

InnoDB의 B+Tree 기능:

1. B Tree가 해결할 수 있는 모든 문제를 해결할 수 있는 B Tree의 변형입니다. B Tree가 해결하는 두 가지 주요 문제는 무엇입니까? (각 노드는 더 많은 키워드와 더 많은 경로를 저장합니다.)

2. 더 강력한 데이터베이스 및 테이블 검색 기능(테이블에서 전체 테이블 검색을 수행하려면 리프 노드만 순회하면 되며 전체 B를 순회할 필요가 없습니다.) +Tree는 모든 데이터를 가져옵니다);

3. B+Tree는 B Tree보다 디스크 읽기 및 쓰기 기능이 더 강력합니다. (루트 노드와 분기 노드는 데이터 영역을 저장하지 않으므로 하나의 노드에 더 많은 키워드, 더 많은 키워드를 저장할 수 있습니다.

4. 정렬 능력이 더 강력합니다(리프 노드에 다음 데이터 영역에 대한 포인터가 있고 데이터가 연결된 목록을 형성하기 때문). 더 안정적입니다(B +Tree는 항상 리프 노드에서 데이터를 가져오므로 IO 수가 안정적입니다).

5. Postscript

이것을 보고 나면 MySQL이 인덱스의 데이터 구조 모델로 B+ 트리를 선택하는 이유를 모두가 알게 될 것입니다.

더 많은 프로그래밍 관련 지식을 보려면

프로그래밍 소개

를 방문하세요! !

위 내용은 MySQL의 인덱스란 무엇입니까? 인덱스 저장 모델의 간략한 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!