MySQL 인덱스 데이터 구조

1. 서문:

우리 생활 속에서는 기차역에서 본 기차 시간표, 사전 명부 등 지표 효과를 볼 수 있는 애플리케이션을 내보냅니다. 그 기능은 획득하려는 데이터의 범위를 지속적으로 좁혀 최종적으로 원하는 결과를 필터링하는 동시에 무작위 이벤트를 순차적 이벤트로 변환하는 인덱스의 기능입니다. 즉, 우리는 항상 동일한 검색 방법을 사용하여 검색합니다. 데이터를 잠급니다(사전의 A-Z 조회).

생활 예 - 기차 타기: 기차를 타고 고향으로 갑니다. 기차를 타고 싶은데 기차 시간표가 없으면 최악의 결과는 모든 기차를 타야 한다는 것입니다. 내가 타고 싶은 기차를 찾기 위해 정차하지만 시간표가 있으면 내가 가고 싶은 기차가 어디에 정차하는지 빨리 알 수 있고, 내가 원하는 기차가 있는지 일일이 확인하는 대신 바로 그 곳으로 갈 수 있다. 로 이동하여 방문 속도를 높입니다. 이 열차 시간표는 데이터베이스의 색인입니다.

2. 디스크 원리:

이 부분은 글과 이론이 많이 포함되어 있어서 읽기 귀찮으신 분들은 읽어보시면 됩니다. 관심이 없더라도 상관없습니다. 다음 장을 읽을 때 이 부분의 결론 하나만 기억하세요.

가능한 한 많은 데이터를 읽으세요. [I/O 상호 작용 횟수를 줄이세요. 운영 체제와 함께].

좋아요, 관심없으시면 건너뛰시고 다음으로 넘어가셔도 됩니다.

데이터베이스 구현은 상대적으로 복잡합니다. 성능을 향상하기 위해 데이터의 일부를 매번 계산을 위해 메모리로 읽어올 수 있습니다. 디스크는 메모리에 액세스하는 것의 약 100,000배이므로 간단한 검색 트리는 복잡한 애플리케이션 시나리오를 충족하기 어렵습니다. 디스크 액세스는 앞에서 언급했으므로 디스크 IO 및 사전 읽기에 대해 간략하게 소개합니다. 디스크에서 데이터를 읽는 것은 기계적 움직임에 따라 달라집니다. 데이터를 읽을 때마다 소요되는 시간은 탐색 시간, 회전 지연의 세 가지 범주로 나눌 수 있습니다. , 전송 시간 부분,
a)·탐색 시간: 자기 암이 지정된 트랙으로 이동하는 데 필요한 시간, 주류 디스크는 일반적으로 5ms 미만입니다. b) 회전 지연: 우리가 자주 듣는 디스크 속도입니다. , 예를 들어 7200rpm 디스크는 분당 7200회 회전할 수 있음을 의미하며, 이는 초당 120회 회전할 수 있음을 의미하며 회전 지연은 1/120/2 = 4.17ms입니다. c)를 참조합니다. 디스크에서 읽기 또는 디스크에 데이터 쓰기 시간은 일반적으로 10분의 1밀리초 정도이며 처음 두 번에 비해 무시할 수 있는 수준입니다.
(매우 상세한 기사를 읽었습니다: http://wdxtub.com/2016/04/16/thin-csapp-3/)

그러면 디스크에 액세스하는 데 걸리는 시간은 디스크입니다. IO 시간은 대략 5+4.17 = 9ms로 상당히 좋은 것 같지만 500-MIPS(초당 백만 명령) 기계는 초당 5억 명령을 실행할 수 있다는 것을 알아야 합니다. 명령은 전기의 특성에 의존하기 때문입니다. 즉, 하나의 IO를 실행하는 데 걸리는 시간에 400,000개의 명령을 실행할 수 있습니다. 데이터베이스에는 수십만, 수백만, 심지어는 수천만 개의 데이터가 포함되는 경우가 많습니다. 9밀리초가 걸릴 때마다 이는 분명히 재앙입니다.

결론: 운영 체제 I/O 상호 작용 횟수를 줄이세요.

(IO에서 읽은 데이터를 페이지마다 호출합니다. 페이지의 구체적인 데이터 크기는 운영 체제에 따라 다르며 일반적으로 4k 또는 8k, 즉 페이지를 읽을 때 데이터가 생성될 때 , 실제로는 1개의 IO만 발생합니다.)

3. 인덱스란:

데이터베이스 시스템을 사용하는 동안 데이터 쿼리는 가장 자주 사용되는 데이터 작업입니다.

가장 기본적인 쿼리 알고리즘은 물론 선형 검색입니다. 테이블을 순회한 후 행 값이 찾으려는 키워드와 동일한지 여부를 행별로 일치시킵니다. 시간 복잡도는 O(n)입니다. 그러나 시간 복잡도가 O(n)인 알고리즘은 작은 테이블과 로드가 적은 데이터베이스에서도 좋은 성능을 얻을 수 있습니다. 하지만 데이터가 증가하면 O(n)의 시간복잡도를 갖는 알고리즘은 명백히 좋지 않으며 성능도 빠르게 저하됩니다.

다행스럽게도 컴퓨터 과학의 발전으로 이진 검색, 이진 검색 등 더 나은 검색 알고리즘이 많이 제공되었습니다. 트리 검색) 등 조금만 분석해 보면 각 검색 알고리즘은 특정 데이터 구조에만 적용할 수 있다는 것을 알 수 있습니다. 예를 들어 이진 검색에서는 검색된 데이터를 정렬해야 하지만 이진 트리 검색은 이진 검색 트리에만 적용할 수 있습니다. 하지만 데이터 자체의 조직 구조는 다양한 데이터 구조를 완벽하게 만족시킬 수 없기 때문에(예를 들어 두 열을 동시에 순서대로 정리하는 것은 이론적으로 불가능합니다.) 따라서 데이터베이스 시스템은 데이터 외에도 특정 데이터 구조를 만족하는 데이터 구조를 유지합니다. 검색 알고리즘은 어떤 방식으로든 데이터를 참조(지시)하여 고급 검색 알고리즘을 이러한 데이터 구조에 구현할 수 있도록 합니다. 이 데이터 구조는 인덱스입니다.

4. MySQL의 B-Tree 인덱스(기술적으로는 B+Tree)

자, 이번 글의 핵심은 여기까지입니다!

MySQL에는 B-Tree 인덱스, Hash 인덱스, Fulltext 인덱스, R-Tree 인덱스의 네 가지 주요 인덱스 유형이 있습니다. 주로 B-Tree 지수를 분석합니다. (B: 균형은 이진 트리가 아닌 균형을 의미합니다)

1. b+ 트리 데이터 구조에 대한 자세한 설명

위 그림은 b+tree인데, (innodb 엔진 아래는 myisam 엔진 아래 B+ 구조와 다릅니다. 직설적으로 말하면 Clustered Index와 Non-Clustered Index의 차이입니다. 자세한 내용은 , 참조:

Mysql-Clustered Index

연한 파란색 블록을 디스크 블록이라고 합니다. 각 디스크 블록에는 여러 데이터 항목이 포함되어 있습니다(짙은 파란색으로 표시됨, 범위: [( M /2)-1, M-1] M은 총 데이터) 및 포인터(노란색으로 표시)입니다. 예를 들어 디스크 블록 1에는 디스크를 나타내는 포인터 P1, P2 및 P3을 포함하여 데이터 항목 17과 35가 포함됩니다. 17보다 작은 블록. P2는 17에서 35 사이의 디스크 블록을 나타내고 P3은 35보다 큰 디스크 블록을 나타냅니다. 실제 데이터는 리프 노드, 즉 3, 5, 9, 10, 13, 15, 28, 29, 36에 존재합니다. 60, 75, 79, 90, 99. 비리프 노드는 실제 데이터(B+의 특성)를 저장하지 않고 검색 방향을 안내하는 데이터 항목만 저장합니다. 예를 들어 17과 35는 실제로 데이터 테이블에 존재하지 않습니다. 🎜>

2. B+ 트리의 검색 과정

그림과 같이 데이터 항목 29를 찾으려면 디스크 블록 1이 디스크에서 메모리로 로드됩니다. 먼저 IO가 발생하면 메모리에서 이진 검색을 사용하여 17과 35 사이의 29를 결정하고 디스크 블록 1의 P2 포인터를 잠급니다. 메모리 시간은 디스크의 IO에 비해 매우 짧기 때문에 무시할 수 있습니다. 디스크 블록 1의 P2 포인터를 디스크에 전달합니다. 주소는 디스크에서 메모리로 디스크 블록 3을 로드합니다. 두 번째 IO는 26과 30 사이에서 발생합니다. 디스크 블록 3의 P2 포인터는 잠겨 있습니다. 세 번째 IO가 발생함과 동시에 메모리가 바이너리 검색을 수행하여 29개를 찾고 쿼리가 종료되어 총 3개의 IO가 발생합니다.

실제 상황은 3레이어입니다. b+ 트리는 수백만 개의 데이터를 표현할 수 있으며, 수백만 개의 데이터를 검색하면 3개의 IO만 있으면 성능이 크게 향상됩니다. 분명히 비용은 매우 높습니다.(질문???, 위에서 언급한 바와 같이 INNOBD의 B+ 트리는 클러스터형 인덱스 유형이며 실제 데이터는 인덱스 리프 노드와 함께 배치됩니다. 그렇다면 질문은 여러 개의 인덱스가 있는 경우 각 인덱스 아래에 데이터가 저장되어 있는 것이 가능한가 하는 것입니다. 디스크 저장 공간이 낭비되는 것일까요? 그렇지 않은 경우에는 과거를 가리키는 포인터를 사용하는 것 같습니다. 구조? )

답변: 각 테이블은 하나의 클러스터형 인덱스만 가질 수 있지만 여러 개가 있을 수 있습니다. 보조 인덱스는 데이터가 아니라 이를 가리키는 포인터이기도 합니다. 데이터가 저장되는 기본 인덱스

3.b+트리 속성

1) 위 분석을 통해 IO 수는 b + 높이 h에 따라 결정된다는 것을 알 수 있습니다. 현재 데이터 테이블의 데이터가 N이고, 각 디스크 블록의 데이터 항목 수를 m이라고 가정하면, 데이터 양 N이 일정할 때, h=㏒(m+1)N이 됩니다. m은 h가 더 작은 반면, m은 더 작습니다. = 디스크 블록의 크기/데이터 항목의 크기. 디스크 블록의 크기는 데이터 페이지의 크기이며, 데이터 항목이 차지하는 공간이 더 작을수록 데이터 항목의 개수는 고정됩니다. 더 많고 트리의 높이 h도 더 낮습니다. 이것이 바로 각 데이터 항목, 즉 인덱스 필드가 최대한 작아야 하는 이유입니다.

부정적인 예로 int는 4바이트를 차지하는데, 이는 bigint 8바이트보다 절반 적은 크기입니다. 이것이 b+ 트리에서 내부 노드 대신 리프 노드에 실제 데이터를 배치해야 하는 이유입니다. 일단 내부 노드에 배치되면 디스크 블록의 데이터 항목이 크게 떨어지므로(위 2부의 원리 참조) 트리가 다음과 같이 됩니다. 높이 증가. 데이터 항목이 1과 같으면 선형 테이블로 변환됩니다.

왼쪽이 구조라면 I/O 개수는 3배, 오른쪽이 선형 테이블이면 I/O 개수는 3배이다. I/O는 6번입니다.

두 가지 결론이 더 있습니다.

1. 인덱스는 작아야 합니다.

2. 유니온을 수행합니다. 인덱스할 때 조인트 필드 수도 적어야 합니다.

2) b+ 트리의 데이터 항목이 (이름, 나이, 성별)과 같은 복합 데이터 구조(다열 인덱스)인 경우 b+ 숫자를 사용하여 왼쪽부터 순서대로 검색 트리를 구성합니다. 오른쪽.

예를 들어 (Zhang San, 20, F)와 같은 데이터가 검색되면 b+ 트리는 먼저 이름을 비교하여 다음 검색 방향을 결정합니다. 이름이 동일하면 나이와 성별이 됩니다. 순서대로 비교하고 마지막으로 검색된 데이터를 얻었지만 (20,F)와 같은 이름이 없는 데이터가 오면 b+ 트리는 검색 트리를 구축할 때 이름이 첫 번째 비교 요소이기 때문에 다음에 확인할 노드를 알 수 없습니다. 그리고 다음에 검색할 곳을 알기 위해서는 먼저 이름을 기준으로 검색해야 합니다.

예를 들어 (Zhang San, F)와 같은 데이터를 검색할 때 b+ 트리는 name을 사용하여 검색 방향을 지정할 수 있지만 다음 필드 age가 누락되어 이름이 다음과 같은 데이터만 검색할 수 있습니다. Zhang San과 같습니다. 성별이 F인 데이터를 찾아서 일치시킵니다. 이는 매우 중요한 속성, 즉 지수의 가장 왼쪽 일치 특성입니다.

은 두 가지 결론을 매핑합니다.

1. 가장 왼쪽의 일치 특성은 결합 인덱스를 왼쪽에서 오른쪽으로 읽습니다.

2. 다중 열 인덱스가 있는 경우 왼쪽에서 오른쪽으로 인덱스를 설정할 필요가 없습니다(a, b, c). 그러면 (a), (a, b)를 설정할 필요가 없습니다

3. 추가 결론: Mysql-index 요약 http://blog.csdn.net/ty_hf/article/details/53526405

위 내용은 Mysql-index 데이터 구조 내용이며, 더 많은 관련 내용은 PHP 중국어 홈페이지(www.kr)를 참고하시기 바랍니다. .php.cn)!