MySQL 인덱스의 데이터 구조와 알고리즘 원리에 대한 자세한 설명
- 高洛峰원래의
- 2017-01-16 15:12:231018검색
요약
이 기사에서는 MySQL 데이터베이스를 연구 대상으로 삼아 데이터베이스 인덱스와 관련된 몇 가지 주제를 논의합니다. MySQL은 많은 스토리지 엔진을 지원하며 다양한 스토리지 엔진은 인덱스에 대해 서로 다른 지원을 갖습니다. 따라서 MySQL 데이터베이스는 BTree 인덱스, 해시 인덱스, 전체 텍스트 인덱스 등과 같은 여러 인덱스 유형을 지원합니다. 혼란을 피하기 위해 이 글에서는 BTree 인덱스에 대해서만 집중적으로 다루겠습니다. BTree 인덱스는 MySQL을 사용할 때 주로 다루는 인덱스이기 때문입니다. 해시 인덱스와 전체 텍스트 인덱스에 대해서는 이번 글에서는 당분간 다루지 않습니다. 존재.
기사의 주요 내용은 세 부분으로 나누어져 있습니다.
첫 번째 부분에서는 주로 데이터 구조와 알고리즘의 이론적 수준에서 MySQL 데이터베이스 인덱스의 수학적 기초를 논의합니다.
두 번째 부분에서는 MySQL 데이터베이스의 MyISAM 및 InnoDB 데이터 스토리지 엔진의 인덱스 아키텍처 구현을 기반으로 클러스터형 인덱스, 비클러스터형 인덱스, 커버링 인덱스 등의 주제를 논의합니다.
세 번째 부분에서는 위의 이론적 근거를 바탕으로 MySQL에서의 고성능 인덱스 활용 전략을 논의한다.
데이터 구조와 알고리즘의 기초
인덱스의 본질
MySQL의 공식 인덱스 정의는 인덱스(Index)는 MySQL이 데이터를 효율적으로 얻을 수 있도록 도와주는 데이터 구조이다. 문장의 백본을 추출하면 인덱스의 본질을 얻을 수 있습니다. 인덱스는 데이터 구조입니다.
우리는 데이터베이스 쿼리가 데이터베이스의 가장 중요한 기능 중 하나라는 것을 알고 있습니다. 우리 모두는 가능한 한 빨리 데이터를 쿼리하기를 원하므로 데이터베이스 시스템 설계자는 쿼리 알고리즘의 관점에서 최적화합니다. 가장 기본적인 쿼리 알고리즘은 물론 선형 검색입니다. O(n)의 복잡성을 갖는 이 알고리즘은 데이터 양이 많을 때 확실히 좋지 않습니다. 다행히도 컴퓨터 과학의 발전으로 이진수와 같은 더 나은 검색 알고리즘이 많이 제공되었습니다. 검색, 이진 트리 검색 등 조금만 분석해 보면 각 검색 알고리즘은 특정 데이터 구조에만 적용할 수 있다는 것을 알 수 있습니다. 예를 들어 이진 검색에서는 검색된 데이터를 정렬해야 하지만 이진 트리 검색은 이진 검색 트리에만 적용할 수 있습니다. 하지만 데이터 자체의 조직 구조는 다양한 데이터 구조를 완벽하게 만족시킬 수 없기 때문에(예를 들어 두 열을 동시에 순서대로 정리하는 것은 이론적으로 불가능합니다.) 따라서 데이터베이스 시스템은 데이터 외에도 특정 데이터 구조를 만족하는 데이터 구조를 유지합니다. 검색 알고리즘은 어떤 방식으로든 데이터를 참조(지시)하여 고급 검색 알고리즘을 이러한 데이터 구조에 구현할 수 있도록 합니다. 이 데이터 구조는 인덱스입니다.
예 보기:
그림 1
그림 1은 가능한 색인 방법 중 하나를 보여줍니다. 왼쪽에는 총 2개의 열과 7개의 레코드가 있는 데이터 테이블이 있습니다. 가장 왼쪽은 데이터 레코드의 물리적 주소입니다(논리적으로 인접한 레코드가 디스크에서 반드시 물리적으로 인접한 것은 아닙니다). Col2의 검색 속도를 높이기 위해 오른쪽에 표시된 것처럼 이진 검색 트리를 유지할 수 있습니다. 각 노드에는 해당 데이터 레코드의 물리적 주소에 대한 포인터와 인덱스 키 값이 포함되어 있습니다. O(log2n)의 이진 검색 복잡도 내에서 해당 데이터를 얻습니다.
진정한 인덱스임에도 불구하고 실제 데이터베이스 시스템은 이진 검색 트리나 그 진화된 변종인 레드-블랙 트리를 사용하여 구현된 경우가 거의 없습니다.
B-Tree 및 B+Tree
현재 대부분의 데이터베이스 시스템 및 파일 시스템은 B-Tree 또는 그 변형 B+Tree를 인덱스 구조로 사용하며, 이는 다음 섹션에서 결합됩니다. 메모리 원리와 컴퓨터 액세스 원리는 B-Tree 및 B+Tree가 인덱싱에 널리 사용되는 이유를 설명합니다. 이 섹션에서는 먼저 데이터 구조의 관점에서 이들을 설명합니다.
B-Tree
B-Tree를 설명하려면 먼저 데이터 레코드를 튜플 [키, 데이터]로 정의합니다. key는 레코드의 키 값입니다. 다양한 데이터 레코드에 대해 , 키는 서로 다릅니다. 데이터는 키를 제외한 데이터 레코드입니다. 그러면 B-Tree는 다음 조건을 만족하는 자료구조이다:
1. d는 1보다 큰 양의 정수인데, 이를 B-Tree의 차수라고 한다.
2. h는 B-Tree의 높이라고 불리는 양의 정수입니다.
3. 각각의 리프가 아닌 노드는 n-1개의 키와 n개의 포인터로 구성됩니다. 여기서 d
4. 각 리프 노드에는 최소한 하나의 키와 두 개의 포인터가 포함되며 최대 2d-1 키와 2d 포인터는 모두 null입니다.
5. 모든 리프 노드의 깊이는 트리 높이 h와 같습니다.
6. 키와 포인터는 서로 간격을 두고 있으며, 노드의 양쪽 끝은 포인터입니다.
7. 노드의 키는 왼쪽에서 오른쪽으로 감소하지 않고 배열됩니다.
8. 모든 노드는 트리 구조를 형성합니다.
9. 각 포인터는 null이거나 다른 노드를 가리킵니다.
10. 포인터가 노드의 맨 왼쪽에 있고 null이 아닌 경우 포인터가 노드를 가리키는 모든 키는 v(key1)보다 작습니다. 여기서 v(key1)은 다음의 값입니다. 노드의 첫 번째 키.
11. 포인터가 노드의 가장 오른쪽에 있고 null이 아닌 경우 포인터가 노드를 가리키는 모든 키는 v(keym)보다 큽니다. 여기서 v(keym)은 다음 값입니다. 노드의 마지막 키.
12. 노드의 왼쪽과 오른쪽에 있는 포인터의 인접한 키가 각각 keyi 및 keyi+1이고 null이 아닌 경우 노드를 가리키는 모든 키는 v(keyi+1)보다 작습니다. v(keyi)보다 큽니다.
그림 2는 d=2인 B-Tree의 개략도입니다.
그림 2
B-Tree의 특성상 B-Tree에서 키로 데이터를 검색하는 알고리즘은 매우 직관적입니다. 루트 노드, 발견되면 해당 노드의 데이터가 반환됩니다. 그렇지 않으면 해당 간격의 포인터가 가리키는 노드를 해당 노드를 찾거나 널 포인터를 찾을 때까지 반복적으로 검색합니다. 성공하고 후자의 검색은 실패합니다. B-Tree에 대한 검색 알고리즘의 의사 코드는 다음과 같습니다.
BTree_Search(node, key)
{
if(node == null) return null;
foreach(node.key)
{
if(node.key[i] == key) return node.data[i];
if(node.key[i] > key) return BTree_Search(point[i]->node);
}
return BTree_Search(point[i+1]->node);
}
data = BTree_Search(root, my_key);B-Tree에 대한 일련의 흥미로운 속성이 있습니다. 예를 들어, d차를 가진 B-Tree가 N개의 키를 인덱스로 가지고 있는 경우입니다. , 해당 트리 높이는 h입니다. 의 상한은 logd((N+1)/2)입니다. 키를 검색하기 위한 노드 수를 찾는 점근적 복잡도는 O(logdN)입니다. 이 점에서 볼 수 있듯이 B-Tree는 매우 효율적인 인덱스 데이터 구조이다.
또한 새로운 데이터 레코드를 삽입하고 삭제하면 B-Tree의 속성이 파괴되므로 삽입, 삭제 시 B-Tree의 속성을 유지하기 위해 트리를 분할, 병합, 전송 등을 해야 합니다. Tree. B-Tree의 수학적 특성과 삽입 및 삭제 알고리즘을 자세히 설명하는 자료가 이미 많기 때문에 이 기사에서는 B-Tree의 내용을 전체적으로 논의할 계획이 없습니다. 관심 있는 친구들은 참고 자료에서 해당 자료를 찾을 수 있습니다. 이 글의 마지막 부분에 있는 칼럼을 읽어보세요.
B+Tree
B-Tree에는 다양한 변형이 있으며 그 중 가장 일반적인 것은 B+Tree입니다. 예를 들어 MySQL은 일반적으로 B+Tree를 사용하여 인덱스 구조를 구현합니다.
B-Tree와 비교했을 때 B+Tree는 다음과 같은 차이점이 있습니다.
1. 각 노드의 포인터 상한은 2d+1이 아닌 2d입니다.
2. 내부 노드는 데이터를 저장하지 않으며, 리프 노드만 포인터를 저장하지 않습니다.
그림 3은 간단한 B+Tree 다이어그램입니다.
그림 3
모든 노드가 동일한 도메인을 갖지 않기 때문에 B+Tree의 리프 노드와 내부 노드는 일반적으로 크기가 다릅니다. 이는 B-Tree와 다른 점으로, B-Tree의 서로 다른 노드에 저장된 키와 포인터의 개수는 일치하지 않을 수 있지만, 각 노드의 도메인과 상한은 일치하므로 구현 시 B-Tree는 동일하게 적용되는 경우가 많습니다. 각 노드의 공간 크기.
일반적으로 B-Tree보다 외부 저장소 인덱스 구조를 구현하는 데 B+Tree가 더 적합합니다. 구체적인 이유는 아래에서 설명할 외부 메모리 및 컴퓨터 액세스 원리와 관련이 있습니다.
순차 액세스 포인터가 포함된 B+Tree
데이터베이스 시스템이나 파일 시스템에서 일반적으로 사용되는 B+Tree 구조는 클래식 B+Tree를 기반으로 최적화되었으며 순차 액세스 포인터가 추가되었습니다.
그림 4
그림 4와 같이 B+Tree의 각 리프 노드에서 인접한 리프 노드에 포인터를 추가하여 A B+를 형성합니다. 순차 액세스 포인터가 있는 트리입니다. 이 최적화의 목적은 간격 액세스 성능을 향상시키는 것입니다. 예를 들어 그림 4에서 18부터 49까지의 키가 있는 모든 데이터 레코드를 쿼리하려면 18을 찾은 후 노드와 포인터를 순차적으로 순회하면 됩니다. 모든 데이터 노드에 동시에 액세스할 수 있으므로 간격 쿼리의 효율성이 크게 향상됩니다.
이 섹션에서는 B-Tree 및 B+Tree에 대해 간략하게 소개합니다. 다음 섹션에서는 B+Tree가 현재 데이터베이스 시스템에서 인덱싱에 선호되는 데이터 구조인 이유를 소개하기 위해 메모리 액세스 원칙을 결합합니다.
B-Tree(B+Tree)를 사용하는 이유
위에서 언급한 것처럼 레드-블랙 트리와 같은 데이터 구조를 사용하여 인덱스를 구현할 수도 있지만 파일 시스템이나 데이터베이스 시스템에서는 일반적으로 B- /+Tree는 인덱스 구조로 사용됩니다. 이 섹션에서는 컴퓨터 구성 원리에 대한 지식을 바탕으로 인덱스로서 B-/+Tree의 이론적 근거를 논의합니다.
일반적으로 인덱스 자체도 매우 크고 메모리에 완전히 저장할 수 없기 때문에 인덱스 파일 형태로 디스크에 저장되는 경우가 많습니다. 이 경우 인덱스 검색 과정에서 디스크 I/O 소비가 발생하게 되며, 메모리 액세스에 비해 I/O 액세스 소비가 몇 배 더 높아지게 되므로 데이터 품질을 평가하는 가장 중요한 지표가 됩니다. 인덱스로서의 구조는 검색 프로세스 중 디스크 I/O 작업 수의 점근적 복잡성입니다. 즉, 인덱스의 구조적 구성은 검색 과정에서 디스크 I/O 액세스 횟수를 최소화해야 합니다. 다음은 먼저 메모리와 디스크 접근의 원리를 소개하고, 이 원리들을 결합하여 B-/+Tree의 효율성을 지표로 분석해 보겠습니다.
메인 메모리 액세스 원리
현재 컴퓨터에 사용되는 메인 메모리는 기본적으로 RAM(Random Read and Write Memory)입니다. 현대 RAM의 구조와 액세스 원리는 비교적 복잡합니다. RAM의 작동 원리를 설명하기 위해 매우 간단한 액세스 모델을 추상화합니다.
사진 5
추상적인 관점에서 메인 메모리는 일련의 저장 장치로 구성된 매트릭스이며, 각 저장 장치는 고정된 크기의 데이터를 저장합니다. 각 저장 장치에는 고유한 주소가 있습니다. 현대 주 메모리의 주소 지정 규칙은 상대적으로 복잡합니다. 여기서는 2차원 주소로 단순화됩니다. 저장 장치는 행 주소와 열 주소를 통해 고유하게 위치할 수 있습니다. 그림 5는 4 x 4 메인 메모리 모델을 보여줍니다.
메인 메모리 접근 과정은 다음과 같습니다.
시스템이 메인 메모리를 읽어야 할 때 주소 신호는 주소 버스에 실려 메인 메모리로 전달됩니다. 메모리는 주소 신호를 읽고, 신호를 분석하고 지정된 저장 장치를 찾은 다음 이 저장 장치의 데이터를 다른 구성 요소가 읽을 수 있도록 데이터 버스에 넣습니다.
메인 메모리에 쓰는 과정은 비슷합니다. 시스템은 쓸 유닛 주소와 데이터를 각각 주소 버스와 데이터 버스에 배치합니다. 메인 메모리는 두 버스의 내용을 읽고 해당 쓰기를 수행합니다. 운영.
여기에서 볼 수 있듯이 메인 메모리 액세스 시간은 액세스 횟수와 선형적으로만 관련되어 있습니다. 기계적 작업이 없기 때문에 두 번 액세스하는 데이터의 "거리"는 영향을 미치지 않습니다. 예를 들어, A0을 먼저 복용하고 A1을 복용하는 데 소요되는 시간은 A0을 먼저 복용하고 D3을 복용하는 것과 같습니다.
디스크 접근의 원칙
위에서 언급한 것처럼 인덱스는 일반적으로 파일 형태로 디스크에 저장되며, 인덱스 검색에는 디스크 I/O 작업이 필요합니다. 디스크 I/O는 메인 메모리와 달리 기계적 이동 비용이 발생하므로 디스크 I/O의 시간 소모가 크다.
그림 6은 디스크의 전체적인 구조를 개략적으로 나타낸 것이다.
그림 6
디스크는 동일한 크기와 동축성을 갖는 원형 디스크로 구성됩니다(각 디스크는 동기식으로 회전해야 함). 디스크 한쪽에는 헤드 브래킷이 있습니다. 헤드 브래킷은 헤드 세트를 고정합니다. 각 헤드는 디스크 내용에 액세스합니다. 자기 헤드는 회전할 수 없지만 디스크의 반경을 따라 이동할 수 있습니다(실제로는 비스듬한 접선 이동). 각 자기 헤드도 동시에 동축이어야 합니다. 즉, 바로 위에서 볼 때 모든 자기 헤드가 어느 위치에서든 겹쳐야 합니다. (그러나 현재는 이러한 제한이 적용되지 않는 다중 헤드 독립 기술이 있습니다.)
그림 7은 디스크 구조의 개략도이다.
그림 7
디스크는 일련의 동심원 고리로 나누어져 있으며, 원의 중심이 디스크의 중심이고, 각 동심원은 모두 동일한 반경을 갖는 트랙이라고 합니다. 트랙은 원통을 형성합니다. 트랙은 반경선을 따라 작은 세그먼트로 나누어지며 각 세그먼트를 섹터라고 하며 각 섹터는 디스크의 가장 작은 저장 단위입니다. 단순화를 위해 아래에서는 디스크에 플래터와 헤드가 하나만 있다고 가정합니다.
디스크에서 데이터를 읽어야 하는 경우 시스템은 데이터의 논리 주소를 디스크로 전송합니다. 디스크의 제어 회로는 주소 지정 논리에 따라 논리 주소를 물리 주소로 변환합니다. 즉, 읽을 데이터가 어느 트랙에 있는지, 어느 섹터에 있는지 결정합니다. 이 섹터의 데이터를 읽으려면 자기 헤드를 이 섹터 위에 배치해야 합니다. 이를 위해서는 해당 트랙에 맞춰 자기 헤드를 움직여야 하며, 이 과정을 탐색이라고 합니다. 그러면 디스크 회전이 헤드 아래에서 회전됩니다. 이 프로세스에 소요되는 시간을 회전 시간이라고 합니다.
지역성 원칙과 디스크 미리 읽기
저장매체의 특성상 디스크 접근 속도가 메인 메모리에 비해 훨씬 느리다. 종종 메인 메모리의 100분의 1을 차지하므로 효율성을 높이려면 디스크 I/O를 최소화해야 합니다. 이 목표를 달성하기 위해 디스크는 엄격하게 요구에 따라 읽는 것이 아니라 매번 미리 읽는 경우가 많습니다. 1바이트만 필요하더라도 디스크는 이 위치에서 시작하여 일정 길이의 데이터를 순차적으로 읽어옵니다. 메모리. 이에 대한 이론적 근거는 컴퓨터 과학의 유명한 지역성 원리입니다.
데이터 조각을 사용하면 일반적으로 근처에 있는 데이터가 즉시 사용됩니다.
프로그램 실행 중에 필요한 데이터는 대개 집중되어 있습니다.
디스크 순차 읽기는 매우 효율적이므로(탐색 시간이 필요하지 않고 회전 시간이 거의 없음) 미리 읽기는 지역성이 있는 프로그램의 I/O 효율성을 향상시킬 수 있습니다.
미리 읽기 길이는 일반적으로 페이지의 정수배입니다. 페이지는 컴퓨터 관리 메모리의 논리적 블록입니다. 하드웨어 및 운영 체제는 주 메모리와 디스크 저장 영역을 동일한 크기의 연속된 블록으로 나누는 경우가 많습니다(많은 운영 체제에서 페이지 크기는 일반적으로 4k입니다). 메인 메모리와 디스크는 페이지 단위로 데이터를 교환합니다. 프로그램이 읽을 데이터가 메인 메모리에 없으면 페이지 폴트 예외가 발생합니다. 이때 시스템은 읽기 신호를 디스크에 보내고 디스크는 데이터의 시작 위치를 찾습니다. 한 페이지 또는 여러 페이지를 거꾸로 읽어 메모리에 로드한 후 비정상적으로 반환되고 프로그램이 계속 실행됩니다.
B-/+Tree 지수의 성과 분석
이제 드디어 B-/+Tree 지수의 성과를 분석할 수 있게 되었습니다.
위에서 언급했듯이 디스크 I/O 시간은 일반적으로 인덱스 구조의 품질을 평가하는 데 사용됩니다. B-Tree 분석부터 시작해 보겠습니다. B-Tree의 정의에 따르면 한 번의 검색을 위해 최대 h개의 노드를 방문해야 함을 알 수 있습니다. 데이터베이스 시스템의 설계자는 디스크 미리 읽기 원칙을 교묘하게 활용하여 노드의 크기를 한 페이지와 동일하게 설정하여 각 노드가 단 하나의 I/O로 완전히 로드될 수 있도록 했습니다. 이 목표를 달성하기 위해서는 실제 B-Tree 구현에 다음과 같은 기술이 사용되어야 합니다.
새로운 노드가 생성될 때마다 한 페이지의 공간을 직접 신청하여 노드가 보장되도록 합니다. 또한 컴퓨터 스토리지 할당은 페이지별로 정렬되므로 노드당 하나의 I/O만 필요합니다.
B-Tree에서 검색하려면 최대 h-1 I/O(루트 노드 상주 메모리)가 필요하며 점근적 복잡도는 O(h)=O(logdN)입니다. 일반적인 실제 적용에서, 아웃 차수 d는 매우 큰 숫자(보통 100 이상)이므로 h는 매우 작습니다(보통 3 이하).
결론적으로 B-Tree를 인덱스 구조로 활용하는 것은 매우 효율적이다.
레드-블랙 트리와 같은 구조의 경우 h는 분명히 훨씬 더 깊습니다. 논리적으로 가까운 노드(부모와 자식)가 물리적으로 멀리 떨어져 있을 수 있으므로 지역성을 활용할 수 없으므로 레드-블랙 트리의 I/O 점근적 복잡도도 O(h)이며 효율성은 분명히 B-트리.
위에서 언급했듯이 B+Tree는 외부 저장소 인덱스에 더 적합합니다. 그 이유는 내부 노드의 외부 차수 d와 관련이 있습니다. 위의 분석을 통해 d가 클수록 인덱스 성능이 좋아지며, 아웃 차수의 상한은 노드에 있는 키와 데이터의 크기에 따라 달라지는 것을 알 수 있습니다.
dmax = Floor(페이지 크기 / (키 크기 + 데이터 크기 + 포인트 크기) ) (페이지 크기 – dmax >= 포인트 크기)
또는
dmax = 바닥(페이지 크기 / (키 크기 + 데이터 크기 + 포인트 크기)) – 1(페이지 크기 – dmax
바닥은 반내림을 의미합니다. B+Tree의 노드에서 데이터 도메인이 제거되므로 더 큰 아웃도와 더 나은 성능을 가질 수 있습니다.
이 장에서는 이론적 관점에서 인덱스와 관련된 데이터 구조 및 알고리즘 문제를 논의합니다. 다음 장에서는 B+Tree가 MySQL에서 인덱스로 구체적으로 어떻게 구현되는지 설명하고 MyISAM 및 InnDB 스토리지도 소개합니다. 엔진에는 비클러스터형 인덱스와 클러스터형 인덱스라는 두 가지 인덱스 구현 형식이 있습니다.
MySQL 인덱스 구현
MySQL에서 인덱스는 스토리지 엔진 수준 개념입니다. 이 문서에서는 주로 MyISAM과 InnoDB의 두 가지 스토리지 엔진에 대해 설명합니다.
MyISAM 인덱스 구현
MyISAM 엔진은 B+Tree를 인덱스 구조로 사용하며 리프 노드의 데이터 필드에는 데이터 레코드의 주소가 저장됩니다. 다음 그림은 MyISAM 인덱스의 개략도입니다.
그림 8
여기 테이블에는 총 3개의 열이 있다고 가정합니다. 그림 8은 MyISAM 테이블의 기본 인덱스(Primary key) 표현입니다. MyISAM의 인덱스 파일은 데이터 레코드의 주소만 저장하는 것을 볼 수 있습니다. MyISAM에서는 기본 인덱스의 키가 고유해야 하는 반면 보조 인덱스의 키는 반복될 수 있다는 점을 제외하면 기본 인덱스와 보조 인덱스(보조 키) 사이에 구조적 차이가 없습니다. Col2에 보조 인덱스를 생성하면 이 인덱스의 구조는 아래와 같습니다.
그림 9
도 B+Tree입니다. 데이터 필드는 데이터 레코드의 주소를 저장합니다. 따라서 MyISAM의 인덱스 검색 알고리즘은 먼저 B+Tree 검색 알고리즘에 따라 인덱스를 검색하는 것입니다. 지정된 Key가 존재하면 해당 데이터 필드의 값을 빼낸 다음 데이터 필드의 값을 다음과 같이 사용합니다. 해당 데이터 레코드를 읽을 주소입니다.
MyISAM의 인덱싱 방식을 "비클러스터형"이라고도 부르는 이유는 InnoDB의 클러스터형 인덱스와 구별하기 위함입니다.
InnoDB 인덱스 구현
InnoDB도 인덱스 구조로 B+Tree를 사용하지만, 구체적인 구현 방법은 MyISAM과 전혀 다릅니다.
첫 번째 큰 차이점은 InnoDB의 데이터 파일 자체가 인덱스 파일이라는 점입니다. 위에서 알 수 있듯이 MyISAM 인덱스 파일과 데이터 파일은 분리되어 있으며 인덱스 파일에는 데이터 레코드의 주소만 저장됩니다. InnoDB에서 테이블 데이터 파일 자체는 B+Tree로 구성된 인덱스 구조이며, 이 트리의 리프 노드 데이터 필드는 완전한 데이터 레코드를 저장합니다. 이 인덱스의 키는 데이터 테이블의 기본 키이므로 InnoDB 테이블 데이터 파일 자체가 기본 인덱스가 됩니다.
사진 10
图10是InnoDB主索引（同时也是数据文件）的示意图，可以看到叶节点包含了完整的数据记录。这种索引叫做聚集索引。因为InnoDB的数据文件本身要按主键聚集，所以InnoDB要求表必须有主键（MyISAM可以没有），如果没有显式指定，则MySQL系统会自动选择一个可以唯一标识数据记录的列作为主键，如果不存在这种列，则MySQL自动为InnoDB表生成一个隐含字段作为主键，这个字段长度为6个字节，类型为长整形。
第二个与MyISAM索引的不同是InnoDB的辅助索引data域存储相应记录主键的值而不是地址。换句话说，InnoDB的所有辅助索引都引用主键作为data域。例如，图11为定义在Col3上的一个辅助索引：
图11
这里以英文字符的ASCII码作为比较准则。聚集索引这种实现方式使得按主键的搜索十分高效，但是辅助索引搜索需要检索两遍索引：首先检索辅助索引获得主键，然后用主键到主索引中检索获得记录。
了解不同存储引擎的索引实现方式对于正确使用和优化索引都非常有帮助，例如知道了InnoDB的索引实现后，就很容易明白为什么不建议使用过长的字段作为主键，因为所有辅助索引都引用主索引，过长的主索引会令辅助索引变得过大。再例如，用非单调的字段作为主键在InnoDB中不是个好主意，因为InnoDB数据文件本身是一颗B+Tree，非单调的主键会造成在插入新记录时数据文件为了维持B+Tree的特性而频繁的分裂调整，十分低效，而使用自增字段作为主键则是一个很好的选择。
下一章将具体讨论这些与索引有关的优化策略。
索引使用策略及优化
MySQL的优化主要分为结构优化（Scheme optimization）和查询优化（Query optimization）。本章讨论的高性能索引策略主要属于结构优化范畴。本章的内容完全基于上文的理论基础，实际上一旦理解了索引背后的机制，那么选择高性能的策略就变成了纯粹的推理，并且可以理解这些策略背后的逻辑。
示例数据库
为了讨论索引策略，需要一个数据量不算小的数据库作为示例。本文选用MySQL官方文档中提供的示例数据库之一：employees。这个数据库关系复杂度适中，且数据量较大。下图是这个数据库的E-R关系图（引用自MySQL官方手册）：
图12
MySQL官方文档中关于此数据库的页面为http://dev.mysql.com/doc/employee/en/employee.html。里面详细介绍了此数据库，并提供了下载地址和导入方法，如果有兴趣导入此数据库到自己的MySQL可以参考文中内容。
最左前缀原理与相关优化
高效使用索引的首要条件是知道什么样的查询会使用到索引，这个问题和B+Tree中的“最左前缀原理”有关，下面通过例子说明最左前缀原理。
这里先说一下联合索引的概念。在上文中，我们都是假设索引只引用了单个的列，实际上，MySQL中的索引可以以一定顺序引用多个列，这种索引叫做联合索引，一般的，一个联合索引是一个有序元组
以employees.titles表为例，下面先查看其上都有哪些索引：
SHOW INDEX FROM employees.titles; +--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+ | Table | Non_unique | Key_name | Seq_in_index | Column_name | Collation | Cardinality | Null | Index_type | +--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+ | titles | 0 | PRIMARY | 1 | emp_no | A | NULL | | BTREE | | titles | 0 | PRIMARY | 2 | title | A | NULL | | BTREE | | titles | 0 | PRIMARY | 3 | from_date | A | 443308 | | BTREE | | titles | 1 | emp_no | 1 | emp_no | A | 443308 | | BTREE | +--------+------------+----------+--------------+-------------+-----------+-------------+------+------------+
从结果中可以到titles表的主索引为
ALTER TABLE employees.titles DROP INDEX emp_no;
这样就可以专心分析索引PRIMARY的行为了。
情况一：全列匹配。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title='Senior Engineer' AND from_date='1986-06-26'; +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
很明显，当按照索引中所有列进行精确匹配（这里精确匹配指“=”或“IN”匹配）时，索引可以被用到。这里有一点需要注意，理论上索引对顺序是敏感的，但是由于MySQL的查询优化器会自动调整where子句的条件顺序以使用适合的索引，例如我们将where中的条件顺序颠倒：
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26' AND emp_no='10001' AND title='Senior Engineer'; +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+ | 1 | SIMPLE | titles | const | PRIMARY | PRIMARY | 59 | const,const,const | 1 | | +----+-------------+--------+-------+---------------+---------+---------+-------------------+------+-------+
效果是一样的。
情况二：最左前缀匹配。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001'; +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+ | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------+
当查询条件精确匹配索引的左边连续一个或几个列时，如
情况三：查询条件用到了索引中列的精确匹配，但是中间某个条件未提供。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'; +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
此时索引使用情况和情况二相同，因为title未提供，所以查询只用到了索引的第一列，而后面的from_date虽然也在索引中，但是由于title不存在而无法和左前缀连接，因此需要对结果进行扫描过滤from_date（这里由于emp_no唯一，所以不存在扫描）。如果想让from_date也使用索引而不是where过滤，可以增加一个辅助索引
首先我们看下title一共有几种不同的值：
SELECT DISTINCT(title) FROM employees.titles; +--------------------+ | title | +--------------------+ | Senior Engineer | | Staff | | Engineer | | Senior Staff | | Assistant Engineer | | Technique Leader | | Manager | +--------------------+
只有7种。在这种成为“坑”的列值比较少的情况下，可以考虑用“IN”来填补这个“坑”从而形成最左前缀：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ('Senior Engineer', 'Staff', 'Engineer', 'Senior Staff', 'Assistant Engineer', 'Technique Leader', 'Manager') AND from_date='1986-06-26'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 7 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
这次key_len为59，说明索引被用全了，但是从type和rows看出IN实际上执行了一个range查询，这里检查了7个key。看下两种查询的性能比较：
SHOW PROFILES; +----------+------------+-------------------------------------------------------------------------------+ | Query_ID | Duration | Query | +----------+------------+-------------------------------------------------------------------------------+ | 10 | 0.00058000 | SELECT * FROM employees.titles WHERE emp_no='10001' AND from_date='1986-06-26'| | 11 | 0.00052500 | SELECT * FROM employees.titles WHERE emp_no='10001' AND title IN ... | +----------+------------+-------------------------------------------------------------------------------+
“填坑”后性能提升了一点。如果经过emp_no筛选后余下很多数据，则后者性能优势会更加明显。当然，如果title的值很多，用填坑就不合适了，必须建立辅助索引。
情况四：查询条件没有指定索引第一列。
EXPLAIN SELECT * FROM employees.titles WHERE from_date='1986-06-26'; +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
由于不是最左前缀，索引这样的查询显然用不到索引。
情况五：匹配某列的前缀字符串。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND title LIKE 'Senior%'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 56 | NULL | 1 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
此时可以用到索引，但是如果通配符不是只出现在末尾，则无法使用索引。（原文表述有误，如果通配符%不出现在开头，则可以用到索引，但根据具体情况不同可能只会用其中一个前缀）
情况六：范围查询。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no < '10010' and title='Senior Engineer'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
范围列可以用到索引（必须是最左前缀），但是范围列后面的列无法用到索引。同时，索引最多用于一个范围列，因此如果查询条件中有两个范围列则无法全用到索引。
EXPLAIN SELECT * FROM employees.titles WHERE emp_no < 10010' AND title='Senior Engineer' AND from_date BETWEEN '1986-01-01' AND '1986-12-31'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 4 | NULL | 16 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
可以看到索引对第二个范围索引无能为力。这里特别要说明MySQL一个有意思的地方，那就是仅用explain可能无法区分范围索引和多值匹配，因为在type中这两者都显示为range。同时，用了“between”并不意味着就是范围查询，例如下面的查询：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no BETWEEN '10001' AND '10010' AND title='Senior Engineer' AND from_date BETWEEN '1986-01-01' AND '1986-12-31'; +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+ | 1 | SIMPLE | titles | range | PRIMARY | PRIMARY | 59 | NULL | 16 | Using where | +----+-------------+--------+-------+---------------+---------+---------+------+------+-------------+
看起来是用了两个范围查询，但作用于emp_no上的“BETWEEN”实际上相当于“IN”，也就是说emp_no实际是多值精确匹配。可以看到这个查询用到了索引全部三个列。因此在MySQL中要谨慎地区分多值匹配和范围匹配，否则会对MySQL的行为产生困惑。
情况七：查询条件中含有函数或表达式。
很不幸，如果查询条件中含有函数或表达式，则MySQL不会为这列使用索引（虽然某些在数学意义上可以使用）。例如：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no='10001' AND left(title, 6)='Senior'; +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+ | 1 | SIMPLE | titles | ref | PRIMARY | PRIMARY | 4 | const | 1 | Using where | +----+-------------+--------+------+---------------+---------+---------+-------+------+-------------+
虽然这个查询和情况五中功能相同，但是由于使用了函数left，则无法为title列应用索引，而情况五中用LIKE则可以。再如：
EXPLAIN SELECT * FROM employees.titles WHERE emp_no - 1='10000'; +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | titles | ALL | NULL | NULL | NULL | NULL | 443308 | Using where | +----+-------------+--------+------+---------------+------+---------+------+--------+-------------+
显然这个查询等价于查询emp_no为10001的函数，但是由于查询条件是一个表达式，MySQL无法为其使用索引。看来MySQL还没有智能到自动优化常量表达式的程度，因此在写查询语句时尽量避免表达式出现在查询中，而是先手工私下代数运算，转换为无表达式的查询语句。
索引选择性与前缀索引
既然索引可以加快查询速度，那么是不是只要是查询语句需要，就建上索引？答案是否定的。因为索引虽然加快了查询速度，但索引也是有代价的：索引文件本身要消耗存储空间，同时索引会加重插入、删除和修改记录时的负担，另外，MySQL在运行时也要消耗资源维护索引，因此索引并不是越多越好。一般两种情况下不建议建索引。
第一种情况是表记录比较少，例如一两千条甚至只有几百条记录的表，没必要建索引，让查询做全表扫描就好了。至于多少条记录才算多，这个个人有个人的看法，我个人的经验是以2000作为分界线，记录数不超过 2000可以考虑不建索引，超过2000条可以酌情考虑索引。
另一种不建议建索引的情况是索引的选择性较低。所谓索引的选择性（Selectivity），是指不重复的索引值（也叫基数，Cardinality）与表记录数（#T）的比值：
Index Selectivity = Cardinality / #T
显然选择性的取值范围为(0, 1]，选择性越高的索引价值越大，这是由B+Tree的性质决定的。例如，上文用到的employees.titles表，如果title字段经常被单独查询，是否需要建索引，我们看一下它的选择性：
SELECT count(DISTINCT(title))/count(*) AS Selectivity FROM employees.titles; +-------------+ | Selectivity | +-------------+ | 0.0000 | +-------------+
title的选择性不足0.0001（精确值为0.00001579），所以实在没有什么必要为其单独建索引。
有一种与索引选择性有关的索引优化策略叫做前缀索引，就是用列的前缀代替整个列作为索引key，当前缀长度合适时，可以做到既使得前缀索引的选择性接近全列索引，同时因为索引key变短而减少了索引文件的大小和维护开销。下面以employees.employees表为例介绍前缀索引的选择和使用。
从图12可以看到employees表只有一个索引
EXPLAIN SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido'; +----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+ | id | select_type | table | type | possible_keys | key | key_len | ref | rows | Extra | +----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+ | 1 | SIMPLE | employees | ALL | NULL | NULL | NULL | NULL | 300024 | Using where | +----+-------------+-----------+------+---------------+------+---------+------+--------+-------------+
如果频繁按名字搜索员工，这样显然效率很低，因此我们可以考虑建索引。有两种选择，建
SELECT count(DISTINCT(first_name))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.0042 | +-------------+ SELECT count(DISTINCT(concat(first_name, last_name)))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.9313 | +-------------+
SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.7879 | +-------------+
选择性还不错，但离0.9313还是有点距离，那么把last_name前缀加到4：
SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees; +-------------+ | Selectivity | +-------------+ | 0.9007 | +-------------+
这时选择性已经很理想了，而这个索引的长度只有18，比
ALTER TABLE employees.employees ADD INDEX `first_name_last_name4` (first_name, last_name(4));
此时再执行一遍按名字查询，比较分析一下与建索引前的结果：
SHOW PROFILES; +----------+------------+---------------------------------------------------------------------------------+ | Query_ID | Duration | Query | +----------+------------+---------------------------------------------------------------------------------+ | 87 | 0.11941700 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' | | 90 | 0.00092400 | SELECT * FROM employees.employees WHERE first_name='Eric' AND last_name='Anido' | +----------+------------+---------------------------------------------------------------------------------+
性能的提升是显著的，查询速度提高了120多倍。
前缀索引兼顾索引大小和查询速度，但是其缺点是不能用于ORDER BY和GROUP BY操作，也不能用于Covering index（即当索引本身包含查询所需全部数据时，不再访问数据文件本身）。
InnoDB的主键选择与插入优化
在使用InnoDB存储引擎时，如果没有特别的需要，请永远使用一个与业务无关的自增字段作为主键。
经常看到有帖子或博客讨论主键选择问题，有人建议使用业务无关的自增主键，有人觉得没有必要，完全可以使用如学号或身份证号这种唯一字段作为主键。不论支持哪种论点，大多数论据都是业务层面的。如果从数据库索引优化角度看，使用InnoDB引擎而不使用自增主键绝对是一个糟糕的主意。
上文讨论过InnoDB的索引实现，InnoDB使用聚集索引，数据记录本身被存于主索引（一颗B+Tree）的叶子节点上。这就要求同一个叶子节点内（大小为一个内存页或磁盘页）的各条数据记录按主键顺序存放，因此每当有一条新的记录插入时，MySQL会根据其主键将其插入适当的节点和位置，如果页面达到装载因子（InnoDB默认为15/16），则开辟一个新的页（节点）。
如果表使用自增主键，那么每次插入新的记录，记录就会顺序添加到当前索引节点的后续位置，当一页写满，就会自动开辟一个新的页。如下图所示：
图13
这样就会形成一个紧凑的索引结构，近似顺序填满。由于每次插入时也不需要移动已有数据，因此效率很高，也不会增加很多开销在维护索引上。
如果使用非自增主键（如果身份证号或学号等），由于每次插入主键的值近似于随机，因此每次新纪录都要被插到现有索引页得中间某个位置：
图14
此时MySQL不得不为了将新记录插到合适位置而移动数据，甚至目标页面可能已经被回写到磁盘上而从缓存中清掉，此时又要从磁盘上读回来，这增加了很多开销，同时频繁的移动、分页操作造成了大量的碎片，得到了不够紧凑的索引结构，后续不得不通过OPTIMIZE TABLE来重建表并优化填充页面。
因此，只要可以，请尽量在InnoDB上采用自增字段做主键。
后记
이 글은 보름간 온오프를 기록했으며, 주요 내용은 위와 같습니다. 나의 MySQL 사용은 초보자 수준이고 데이터베이스 튜닝에 대한 경험이 많지 않기 때문에 이 기사가 어느 정도 안락한 연습이라는 것은 부인할 수 없습니다. 여기에서 데이터베이스 인덱스 조정을 수행하세요. 그냥 내 개인 공부 노트로 여기세요.
사실 데이터베이스 인덱스 튜닝은 기술적인 활동이며 이론에만 의존할 수 없습니다. 실제 상황은 끊임없이 변화하고 MySQL 자체에는 쿼리 최적화 전략, 다양한 구현 차이 등 매우 복잡한 메커니즘이 있기 때문입니다. 엔진 상황은 더욱 복잡해집니다. 그러나 동시에 이러한 이론은 인덱스 튜닝의 기초가 됩니다. 이론을 이해해야만 튜닝 전략에 대한 합리적인 추론을 할 수 있고 그 뒤에 있는 메커니즘을 이해할 수 있습니다. 그런 다음 실제적인 지속적인 실험과 탐색을 결합하면 진정한 의미의 튜닝이 가능해집니다. MySQL의 효율적인 사용을 목적으로 합니다.
또한 MySQL 인덱스와 그 최적화는 매우 광범위한 범위를 다루며, 이 기사에서는 그 중 일부만 다룹니다. 예를 들어, 인덱스 최적화 및 정렬(ORDER BY) 관련 인덱스 포함은 이 기사에서 다루지 않습니다. MySQL은 B-Tree 인덱스 외에도 다양한 엔진을 기반으로 해시 인덱스, 전체 텍스트 인덱스 등을 지원합니다. . 이 기사에서는 다루지 않습니다. 기회가 된다면 이 글에서 다루지 못한 부분도 추가하고 싶습니다.
참고자료
[1] Baron Scbwartz 외, Wang Xiaodong 외 번역, High Performance MySQL Press, 2010
[2] 작성: Michael Kofler, Yang Xiaoyun 등이 번역함5, People's Posts and Telecommunications Publishing House, 2006
[3] Jiang Chengyao 작성, 2011년;
[4] D Comer, Ubiquitous B-tree; ACM Computing Surveys(CSUR), 1979
[5] Codd, E. F.(1970). 데이터 뱅크". Communications of the ACM, Vol. 13, No. 6, pp. 377-387
[6] MySQL5.1 참조 매뉴얼 – http://dev.mysql.com/doc / refman/5.1/zh/index.html
MySQL 인덱스의 데이터 구조와 알고리즘 원리에 대한 자세한 설명은 PHP 중국어 웹사이트를 참고하세요!