MySQL 인덱스 구조에 대한 심층적인 이해

이 글에서는 인덱스 구조와 관련된 이슈를 주로 소개하는 mysql 관련 지식을 소개합니다. 그렇다면 인덱스의 구조는 무엇일까요? 인덱싱이 왜 그렇게 빠를 수 있나요? 아래 내용을 살펴보겠습니다. 모두에게 도움이 되기를 바랍니다.

추천 학습: mysql 튜토리얼

데이터베이스 저장 장치

우선, 지속성을 달성하려면 인덱스를 통해 쿼리할 때만 인덱스를 하드 디스크에 저장할 수 있다는 점을 알아야 합니다. , 하드디스크에서는 I/O 작업이 발생하므로 인덱스를 설계할 때는 검색 횟수를 최대한 줄여 I/O 시간을 줄여야 합니다.

또한 매우 중요한 원칙을 알아야 합니다. 데이터베이스 관리 저장 공간의 기본 단위는 페이지(Page)이며, 여러 행의 레코드(Row)가 한 페이지에 저장됩니다. 页(Page)，一个页中存储多条行记录(Row)。

计算机系统对磁盘 I/O 会做预读优化，当一次I/O时，除了当前磁盘地址的数据以外，还会把相邻的数据也读取到内存缓冲池中，每一次 I/O 读取的数据成为一页，InnoDB 默认的页大小是 16KB。
连续的 64 个页组成一个区(Extent)，一个或多个区组成一个段(Segment)，一个或多个段组成表空间(Tablespace)。InnoDB 有两种表空间类型，共享表空间表示多张表共享一个表空间，独立表空间表示每张表的数据和索引全部存在独立的表空间中。

数据页结构如下（图源：极客时间《MySQL 必知必会》）：

数据页的 7 个结构内容可以大致分为以下三类：

• 文件通用部分，用于校验页传输完整
  • 文件头（File Header）: 表述页信息，文件头中使用 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 构成一个双向链表，分别指向前后的数据页。
  • 页头（File Header）：记录页的状态信息
  • 文件尾（File Trailer）: 校验页是否完整
• 记录部分，用于存储数据记录
  • 最大最小记录（Infimum/Supremum）：虚拟的行记录，表示数据页的最大记录和最小记录。
  • 用户记录（User Record）和空闲空间（Free Space）: 用于存储数据行记录内容
• 索引部分，用于提高记录的检索效率
  • 页目录（Page Directory）：存储用户记录的相对位置

详情可参考淘宝的数据库内核月报

索引数据结构

很自然的，我们会想到查找算法中涉及到的一些常用数据结构，比如二叉查找树，二叉平衡树等等，实际上，Innodb 的索引是用 B+ 树

컴퓨터 시스템은 디스크 I/O에 대해 미리 읽기 최적화를 수행합니다. I/O가 수행되면 현재 디스크 주소의 데이터 외에도 인접한 데이터도 디스크로 읽혀집니다. 메모리 버퍼 풀에서는 각 I/O가 읽는 데이터가 1페이지가 되며 InnoDB의 기본 페이지 크기는 16KB입니다.

64개의 연속 페이지가 하나의 익스텐트, 하나 이상의 익스텐트는 세그먼트를 형성하고, 하나 이상의 세그먼트는 테이블스페이스를 형성합니다. InnoDB에는 두 가지 테이블스페이스 유형이 있습니다. 공유 테이블스페이스는 여러 테이블이 하나의 테이블스페이스를 공유한다는 의미입니다. 독립 테이블스페이스는 각 테이블의 데이터와 인덱스가 모두 독립된 테이블스페이스에 저장된다는 의미입니다.

데이터 페이지의 구조는 다음과 같습니다(출처: Geek Time "Must Know MySQL"):
데이터 페이지의 7개 구조적 내용은 대략 다음 세 가지 범주로 나눌 수 있습니다.

• 파일의 일반적인 부분, 확인하는 데 사용됩니다. 페이지 전송이 완료되었음을 나타냅니다.
• 파일 헤더: 페이지 정보를 표현합니다. FIL_PAGE_PREV 및 FIL_PAGE_NEXT는 파일 헤더에 사용되어 각각 이전 및 다음 데이터 페이지를 가리키는 이중 연결 목록을 구성합니다.
• 파일 헤더: 페이지의 상태 정보 기록
• 파일 트레일러: 페이지 완료 여부 확인

기록

• 최대 및 최소 레코드(Infimum/Supremum): 가상 행 레코드로, 데이터 페이지의 최대 레코드와 최소 레코드를 나타냅니다.
• 사용자 레코드 및 여유 공간: 데이터 행 레코드 내용을 저장하는 데 사용됩니다.

인덱스 부분, 레코드 검색 효율성을 향상하는 데 사용됩니다.

• 페이지 디렉토리: 사용자 기록의 상대적 위치를 저장합니다.

자세한 내용은 타오바오의 데이터베이스 커널 월간 보고서를 참조하세요
인덱스 데이터 구조

당연히 우리는 생각할 것입니다 이진 검색 트리, 이진 균형 트리 등과 같은 검색 알고리즘과 관련된 몇 가지 일반적인 데이터 구조입니다. 실제로 Innodb의 인덱스는 B+ 트리를 사용하여 달성합니다. 이 인덱스 구조가 왜 선택되었습니다.

이진 트리의 한계

먼저 이진 검색 트리의 정의를 간단히 살펴보겠습니다. 이진 검색 트리에서 찾으려는 키가 루트 노드보다 크면 올바른 하위 트리에서 검색합니다. 루트 노드보다 작다면, 키를 찾을 때까지 왼쪽 하위 트리에서 검색하세요. 시간 복잡도는 O(logn)입니다. 예를 들어, 시퀀스 [4,2,6,1,3,5,7]은 다음과 같은 이진 검색 트리를 생성합니다.

그러나 일부 특별한 경우에는 이진 트리의 깊이가 매우 커집니다. [1,2,3,4,5,6,7]과 같이 다음과 같은 트리가 생성됩니다.

🎜🎜 다음 상황에서는 최악의 경우 원하는 결과를 찾는 데 7번이 걸리며 쿼리는 다음과 같습니다. 시간은 O(n)이 됩니다. 🎜🎜이러한 상황을 최적화하기 위해 균형 잡힌 이진 검색 트리(AVL 트리)가 있습니다. AVL 트리는 왼쪽과 오른쪽 하위 트리의 높이 차이가 1을 초과하지 않는 트리를 말합니다. 검색 시간 복잡도는 O입니다. (logn)은 이미 상대적으로 이상적인 검색 트리이지만, 수천만 행의 레코드로 구성된 데이터베이스에서는 트리의 깊이가 여전히 매우 높으므로 여전히 가장 이상적인 구조는 아닙니다. 🎜🎜B 트리🎜🎜그래서 이진 트리에서 N-ary 트리로 확장하면 N-ary 트리가 트리의 깊이를 크게 줄일 수 있다고 상상하기 쉽습니다. 실제로는 4계층 트리입니다. 구조는 이미 수십 테라바이트의 데이터를 지원할 수 있습니다. 🎜🎜B-트리(Balance Tree)는 이러한 N-ary 트리입니다. B-트리는 B-트리라고도 하며 다음 정의를 충족합니다. 🎜 k를 B-트리의 차수로 지정하여 각 노드의 자식 수를 나타냅니다. 최대 노드를 가질 수 있습니다), 🎜

1. 각 디스크 블록에는 최대 k - 1 个关键字 和 k 자식 노드에 대한 포인터가 포함됩니다.
2. 리프 노드에는 키워드만 있고 자식 노드 포인터는 없습니다.
3. 각 노드의 키워드는 작은 것부터 큰 것 순으로 정렬되며, 각 키에 있는 모든 키는 단어의 왼쪽 하위 트리는 그보다 작고 오른쪽 하위 트리의 모든 키는 그보다 큽니다.
4. 모든 리프 노드는 동일한 레이어에 있습니다.

위에서 언급했듯이 각 I/O는 한 페이지 크기의 디스크 블록의 데이터를 미리 읽습니다. 디스크 블록의 내용은 I/O의 구조를 나타내는 데 사용됩니다. tree는 다음과 같습니다(출처: Ji 게스트 타임에 SQL을 알아야 합니다):

B-tree도 정렬됩니다. 자식 노드 포인터는 키워드보다 1이 더 많아야 하므로 키워드를 사용하여 세그먼트를 나눌 수 있습니다. 그림의 예에서와 같이 각 A 노드에는 디스크 블록 2와 같이 2개의 키워드와 3개의 하위 노드가 있습니다. 첫 번째 바이트 포인트의 키워드 3, 5는 자신의 첫 번째 하위 노드 8보다 작습니다. 두 번째 자식 노드의 9, 10은 8과 10 사이입니다. 12와 12 사이에서 세 번째 자식 노드의 값은 13과 15로 두 번째 자식 노드 12보다 큽니다.

지금 9를 찾고 싶다고 가정하면 단계는 다음과 같습니다.

1. 루트 노드 디스크 블록 1(17,35)과 비교하면 17보다 작습니다. 디스크에 해당하는 포인터 P1에서 계속 검색합니다. 블록 2
2. 및 디스크 블록 2(8,12) 둘 사이에 있는 비교를 통해 디스크 블록 6
3. 에 해당하는 포인터 P2에서 계속 검색하여 디스크 블록 6(9,10)과 비교하면 다음을 확인할 수 있습니다. 9

이 발견되었습니다. 많은 비교 작업이 이루어졌지만 사전 읽기로 인해 디스크 블록 내 비교가 메모리에서 수행되므로 디스크 I/O를 소비하지 않습니다. 위 작업에는 3개의 I/O만 필요합니다. Os는 이상적인 구조입니다.

B+ 트리 인덱스

B+ 트리는 B 트리를 기반으로 더욱 개선되었습니다. B+ 트리와 B 트리의 차이점은 다음과 같습니다.

1. B+ 트리가 구성되는 방식은 상위 노드의 키워드에 대한 것입니다. 왼쪽 하위 트리의 모든 키워드는 그보다 작고, 오른쪽 하위 트리의 모든 키워드는 그보다 크거나 같습니다.
2. 비리프 노드는 인덱싱에만 사용되며 데이터 레코드를 저장하지 않습니다.
3. 부모의 키워드 node는 자식 노드에도 나타나며 자식 노드의 최대값(또는 최소값)입니다.
4. 모든 키워드는 리프 노드에 나타나고 리프 노드는 작은 것부터 큰 것까지 정렬된 순서가 지정된 연결 목록을 형성합니다.

예제는 다음과 같습니다. 이 예에서는 상위 노드의 키워드가 모두 하위 노드 간의 최소값입니다(출처: Geek Time SQL이 알아야 함).
키워드를 찾고 싶다고 가정합니다. 16에서 검색 단계는 다음과 같습니다.

1. 루트 노드 디스크 1(1,18,35)과 비교하고, 16은 1과 18 사이에 있으며, 디스크 2를 가리키는 포인터 P1을 가져옵니다.
2. 디스크 2(1,8)를 찾습니다. ,14), 16은 14보다 큽니다. 포인터 P3을 가져오고 디스크 7
3. 디스크 7(14,16,17)을 찾고 16

B+ 트리 장점:

1. 내부 노드는 데이터를 저장하지 않습니다. 그래서 각 내부 노드가 저장할 수 있는 레코드의 개수는 B 트리보다 훨씬 크고, 트리의 높이는 낮으며, I/O는 적고, 각 I/O가 읽는 데이터 페이지에는 더 많은 콘텐츠가 포함됩니다
2. 범위 지원 가능 쿼리는 리프 노드로 구성된 순서 연결 리스트를 직접 순회하면 됩니다
3. 모든 데이터는 리프 노드에 저장되므로 쿼리 효율이 더 안정적입니다

HASH 인덱스

MySQL의 메모리 저장 엔진의 기본 인덱스 구조는 해시 인덱스입니다. 특정 알고리즘(예: MD5, SHA1, SHA2 등)을 사용하여 임의 길이의 입력을 고정 길이의 출력으로 변환하는 해시 함수라는 함수입니다. 해시 함수에 대한 자세한 소개는 Baidu Encyclopedia를 참조하세요.

해시 검색 효율성은 O(1)로 매우 효율적입니다. Python의 dict, golang의 맵 및 Java의 해시 맵은 모두 Redis와 같은 Key-Value 데이터베이스도 Hash로 구현됩니다.

정확한 검색을 위해서는 B+ 트리 인덱스보다 해시 인덱스가 더 효율적이지만, 해시 인덱스에는 몇 가지 한계가 있어 가장 주류 인덱스 구조는 아닙니다.

1. 해시 인덱스가 가리키는 데이터는 순서가 없기 때문에 범위 쿼리가 불가능하며 ORDER BY 정렬도 지원하지 않습니다.
2. 해시는 정확히 일치하므로 퍼지 쿼리를 수행할 수 없습니다.
3. 해시 인덱스는 조인트 인덱스의 가장 왼쪽 일치 원칙을 지원하지 않으며, 조인트 인덱스는 완전한 일치가 있을 때만 적용됩니다. Hash 인덱스는 각 인덱스의 Hash 값을 별도로 계산하는 것이 아니라 여러 인덱스를 병합한 후 함께 Hash 값을 계산하여 Hash 값을 계산하기 때문입니다.
4. 인덱싱된 필드에 중복된 값이 많으면 많은 해시 충돌이 발생하고 쿼리에 많은 시간이 소요됩니다.

위의 이유로 Mysql InnoDB 엔진은 Hash 인덱스를 지원하지 않지만 메모리 구조에 Adaptive Hash index 기능이 있습니다. 특정 인덱스 값이 매우 자주 사용되는 경우 B+ 트리를 기반으로 합니다. index 해시 인덱스를 자동으로 생성하여 쿼리 성능을 향상시킵니다.

적응형 해시 인덱스는 해시 인덱스를 사용하여 B+ 트리 인덱스에 페이지 주소를 저장하고 해당 리프 노드를 빠르게 찾는 "인덱스 인덱스"로 이해될 수 있습니다. innodb_adaptive_hash_index변수를 통해 보실 수 있습니다.

추천 학습: mysql 튜토리얼

위 내용은 MySQL 인덱스 구조에 대한 심층적인 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!