MySQL 인덱스가 쿼리 효율성을 이렇게나 향상시킬 수 있는 이유는 무엇일까요?

Background

데이터베이스를 최적화할 때 모두가 인덱스에 대해 이야기할 것이라고 믿습니다. 그리고 저도 예외는 아닙니다. 기본적으로 데이터 구조 최적화와 페이지 캐싱 등에 대해서는 누구나 대답할 수 있습니다. 위에 몇 문장이 있지만, Alibaba P9과의 인터뷰에서 다음과 같은 질문을 받았습니다. 컴퓨터 수준에서 인덱스 데이터를 로드하는 프로세스에 대해 이야기할 수 있습니까? (IO에 대한 이야기를 하고 싶었을 뿐입니다.)

그 자리에서 죽었습니다.... 컴퓨터 네트워크와 운영 체제에 대한 기본 지식이 정말 저의 사각지대이기 때문에 나중에 보충하고 시작하겠습니다. 컴퓨터에 데이터를 로드하는 방법에 대해 이야기하고, 다른 각도에서 인덱싱에 대해 이야기해 보겠습니다.

Text

MySQL의 인덱스는 본질적으로 데이터 구조입니다

먼저 컴퓨터의 데이터 로딩을 이해해 봅시다.

디스크 IO 및 사전 읽기:

먼저 디스크 IO에 대해 이야기해 보겠습니다. 데이터를 읽을 때마다 탐색, 지점 탐색 및 메모리에 복사3단계가 필요합니다. 작동하다.

Seektime은 자기 팔이 지정된 트랙으로 이동하는 데 걸리는 시간으로, 일반적으로 5ms 미만입니다.

Seek point는 트랙에서 데이터가 존재하는 지점을 찾는 것입니다. 평균 시간은 반 회전 시간, 7200rpm 디스크의 경우 평균 지점 탐색 시간은 600000/7200/2=4.17ms입니다.

메모리에 복사하는 시간은 매우 빠르며 이는 이전 두 개에 비해 무시할 수 있습니다. 회이므로 한 회 평균 시간은 약 9ms입니다. 빠른 것 같지만 데이터베이스에 있는 수백만 개의 데이터를 처리하는 데 9000초가 걸리므로 이는 분명 재난 수준입니다.

디스크 IO는 매우 비용이 많이 드는 작업이라는 점을 고려하여 컴퓨터 운영 체제는 IO가 수행될 때 현재 디스크 주소의 데이터뿐만 아니라 인접한 데이터도 미리 읽기를 최적화했습니다. 컴퓨터가 특정 주소의 데이터에 액세스하면 인접한 데이터에도 빠르게 액세스되기 때문에 데이터도 메모리 버퍼로 읽혀집니다.

페이지마다 IO에서 읽은 데이터를 호출합니다. 페이지의 구체적인 데이터 크기는 운영 체제에 따라 다릅니다. 즉, 실제로는 페이지의 데이터를 읽을 때입니다. IO가 한 번 발생했습니다.

(졸업 직후에 문득 들었던 질문이 생각났습니다. 64비트 운영 체제에서 Java의 int 유형은 몇 바이트를 차지합니까? 최대값은 무엇입니까? 이유는 무엇입니까?)

그럼 데이터베이스를 최적화하고 싶습니다. 쿼리를 실행하려면

디스크 IO 작업을 최소화해야 인덱스가 나타납니다.

인덱스란 무엇인가요?

MySQL의 공식 인덱스 정의는 다음과 같습니다. 인덱스(Index)는 MySQL이 데이터를 효율적으로 얻을 수 있도록 돕는 데이터 구조입니다.

MySQL官方对索引的定义为：索引(Index)是帮助MySQL高效获取数据的数据结构。

MySQL 中常用的索引在物理上分两类，B-树索引和哈希索引。

本次主要讲BTree索引。

BTree索引

BTreeMySQL에서 일반적으로 사용되는 인덱스는 물리적으로 B-트리 인덱스와 해시 인덱스의 두 가지 범주로 나뉩니다.

이번에는 BTree 인덱스에 대해 주로 이야기하겠습니다.

• BTree 인덱스

• BTree는 다중 방향 균형 검색 트리라고도 합니다. m-fork BTree의 특징은 다음과 같습니다.
트리의 각 노드에는 최대 m개의 하위 항목이 포함됩니다.
• 루트 노드와 리프 노드를 제외하고 각 노드에는 최소한 [ceil(m/2)]개의 하위 노드가 있습니다(ceil()는 반올림됨).
• 루트 노드가 리프 노드가 아닌 경우 하위 노드가 두 개 이상 있어야 합니다.

모든 리프 노드는 동일한 레이어에 있습니다.

각각의 리프가 아닌 노드는 n개의 키와 n+1개의 포인터로 구성됩니다. 여기서 [ceil(m/2)-1]

이것은 3개의 포크가 있는 BTree 구조 다이어그램입니다(예를 들어 실제로는 많은 포크가 있음). 각 블록을 디스크 블록 또는 운영 체제의 IO라고 합니다. 메모리에서 콘텐츠를 읽을 때, 한 블록은 4개 섹터에 해당합니다. 보라색은 디스크 블록의 데이터 키를 나타내고, 노란색은 데이터를 나타내고, 파란색은 다음 디스크 블록의 위치를 ​​가리키는 포인터 p를 나타냅니다.

키 29로 데이터를 찾는 과정을 시뮬레이션해 보겠습니다.

1. 루트 노드 포인터에 따라 파일 디렉터리의 루트 디스크 블록 1을 읽습니다. [디스크 IO 작업

1회]

2. 디스크 블록 1에는 17, 35 및 3개의 포인터 데이터가 저장됩니다. 우리는 173. p2 포인터에 따라 디스크 블록 3을 찾아 읽습니다. [디스크 IO 작업🎜2회🎜]🎜🎜4. 디스크 블록 3에는 26, 30 및 3개의 포인터 데이터가 저장됩니다. 우리는 265. p2 포인터에 따라 디스크 블록 8을 찾아 읽습니다. [디스크 IO 작업 3회]

6, 디스크 블록 8은 28, 29를 저장합니다. 29를 찾고 29에 해당하는 데이터를 얻습니다.

BTree 인덱스는 디스크 I/O가 역할을 할 때마다 메모리로 가져온 데이터를 만들어 쿼리 효율성을 향상시키는 것을 볼 수 있습니다.

그런데 최적화할 수 있는 게 있을까요?

그림을 보면 각 노드에는 데이터의 키 값뿐만 아니라 데이터 값도 포함되어 있음을 알 수 있습니다. 각 페이지의 저장 공간은 제한되어 있으며, 데이터 데이터가 크면 각 노드(즉, 한 페이지)에 저장할 수 있는 키의 수가 매우 적습니다. B - Tree의 깊이가 커져 쿼리 중 디스크 I/O 수가 증가하여 쿼리 효율성에 영향을 미칩니다.

B+트리 인덱스

B+Tree是在B-Tree를 기반으로 한 최적화로 외부 저장소 인덱스 구조 구현에 더 적합합니다. B+Tree에서는 모든 데이터 레코드 노드가 키 값 순서로 동일한 레이어의 리프 노드에 저장되며, 리프가 아닌 노드에는 키 값 정보만 저장되므로 각 노드에 저장되는 키 값의 수가 크게 늘어날 수 있습니다. node.B+Tree의 높이를 줄입니다.

B+Tree는 B-Tree와 몇 가지 차이점이 있습니다.

Non-leaf 노드는 키 값 정보만 저장하고, 데이터 레코드는 이전 섹션에서 B-Tree를 최적화합니다. B+Tree의 리프가 아닌 노드에는 키 값 정보만 저장되므로 B+Tree의 높이가 특히 낮은 수준으로 압축될 수 있습니다.

구체적인 데이터는 다음과 같습니다.

InnoDB 스토리지 엔진의 페이지 크기는 16KB입니다. 일반 테이블의 기본 키 유형은 INT(4바이트 점유) 또는 BIGINT(8바이트 점유)입니다. 또한 일반적으로 4 또는 8바이트이므로 한 페이지(B+Tree의 한 노드)에는 약 16KB/(8B+8B)=1K 키 값이 저장됩니다(추정이므로 계산의 편의를 위해 값은 여기서 K의 는〖10〗^3)입니다.

즉, 깊이가 3인 B+Tree 인덱스는 10^3 10^3 10^3 = 10억 개의 레코드를 유지할 수 있습니다. (이 계산 방법에는 오류가 있으며 리프 노드는 계산되지 않습니다. 리프 노드를 계산하면 실제로 깊이는 4입니다.)

10억 개 중에서 원하는 데이터를 찾으려면 3번의 IO 작업만 수행하면 됩니다. 9000초 분량의 원래 100만개 데이터와 비교하면 월레스가 얼마나 나은지 모르겠습니다.

그리고 일반적으로 B+Tree에는 두 개의 헤드 포인터가 있습니다. 하나는 루트 노드를 가리키고 다른 하나는 가장 작은 키워드가 있는 리프 노드를 가리키며 모든 리프 노드(즉, 데이터 노드) 사이에는 체인 링 구조가 있습니다. 따라서 B+Tree에 대한 기본 키 범위 검색 및 페이징 검색 외에도 루트 노드부터 무작위 검색을 수행할 수도 있습니다.

데이터베이스의 B+Tree 인덱스는 클러스터형 인덱스와 보조 인덱스로 나눌 수 있습니다.

위의 B+Tree 예시 다이어그램을 데이터베이스에 구현한 것은 클러스터형 인덱스입니다. 클러스터형 인덱스의 B+Tree에 있는 리프 노드에는 테이블 전체의 행 레코드 데이터가 저장됩니다. 클러스터형 인덱스는 보조 인덱스입니다. 리프 노드에는 행 레코드의 모든 데이터가 포함되어 있지 않지만 해당 행 데이터를 저장하는 클러스터형 인덱스 키, 즉 기본 키가 포함되어 있습니다.

보조 인덱스를 통해 데이터를 쿼리할 때 InnoDB 스토리지 엔진은 보조 인덱스를 순회하여 기본 키를 찾은 다음 기본 키를 통해 클러스터형 인덱스에서 전체 행 레코드 데이터를 찾습니다.

인덱스가 쿼리 속도를 높이고 MySQL의 처리 성능을 향상시킬 수 있지만 인덱스를 과도하게 사용하면 다음과 같은 단점이 발생할 수도 있습니다.

• 인덱스를 생성하고 유지하는 데 시간이 걸리며 이 시간은 시간이 지남에 따라 변합니다. 데이터의 양으로.
• 데이터 테이블이 차지하는 데이터 공간 외에도 각 인덱스도 일정량의 물리적 공간을 차지합니다. 클러스터형 인덱스를 만들려면 필요한 공간이 더 커집니다.
• 테이블의 데이터를 추가, 삭제, 수정하는 경우 인덱스를 동적으로 유지해야 하므로 데이터 유지 속도가 저하됩니다.

참고: 인덱스는 어떤 경우에는 쿼리 속도를 높일 수 있지만 어떤 경우에는 효율성이 떨어집니다.

지수는 효율성을 높이는 하나의 요소일 뿐이므로 지수를 구축할 때는 다음 원칙을 따라야 합니다.

• 자주 검색되는 열에 인덱스를 생성하면 검색 속도를 높일 수 있습니다.
• 컬럼에 기본 키로 인덱스를 생성하고, 컬럼의 고유성을 강화하고, 테이블 내 데이터의 배열 구조를 정리합니다.
• 테이블 조인에 자주 사용되는 열에 인덱스를 생성하세요. 이러한 열은 주로 외래 키이므로 테이블 조인 속도를 높일 수 있습니다.
• 인덱스가 이미 정렬되어 있어 지정된 범위가 연속되어 있기 때문에 범위 기반으로 자주 검색해야 하는 열에 인덱스를 만듭니다.
• 자주 정렬이 필요한 열에 인덱스를 생성합니다. 인덱스는 이미 정렬되어 있으므로 쿼리할 때 인덱스 정렬을 사용하면 쿼리 정렬 속도를 높일 수 있습니다.
• WHERE 절을 자주 사용하는 열에 인덱스를 생성하면 조건 판단 속도가 빨라집니다.

이제 모두가 인덱스가 왜 그렇게 빠를 수 있는지 알고 있습니다. 사실, 인덱스 구조는 데이터베이스의 IO 횟수를 최소화할 수 있습니다. . .

요약

인터뷰에 관한 한 실제로 많은 지식을 쉽게 익힐 수 있지만, 학습을 위해서는 컴퓨터의 기본에 깊이 들어가야 하는 내용을 많이 발견하게 됩니다. 많은 사람들이 나에게 어떻게 기억해야 하는지 묻는다. 살 게 너무 많아서 배우는 것 자체도 사실 굉장히 무력한 일인데, 열심히 배워보면 어떨까? 즐기는 법을 배우려면? 최근에는 기초도 공부하고 있는데, 나중에 컴퓨터 기초와 네트워크 관련 지식을 업데이트하기 시작할 예정입니다.

알수록 모르는 것이 많아지는 아오빙입니다.

Talents의 【三连】은 Ao Bing 창작의 가장 큰 동기가 됩니다. 이 블로그에 오류나 제안 사항이 있으면 탤런트들이 메시지를 남겨주세요!

더 많은 관련 무료 학습 권장사항: mysql 튜토리얼(동영상)

위 내용은 MySQL 인덱스가 쿼리 효율성을 이렇게나 향상시킬 수 있는 이유는 무엇일까요?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!