한 기사로 MySQL의 인덱스 이해하기

인덱스란 무엇인가요?

인덱스는 데이터 쿼리의 효율성을 향상시키는 기능을 가진 데이터 구조입니다. 일반적인 은유는 그것을 책의 카탈로그와 비교하는 것입니다. 목차를 통해 특정 장의 내용이 위치한 페이지를 정확하게 찾을 수 있습니다.

데이터의 양이 적을 때는 실제로 인덱스를 사용해도 의미가 없습니다. 인덱스가 없더라도 컴퓨터가 데이터를 하나씩 탐색하는 데는 많은 시간이 걸리지 않습니다. 데이터의 양이 많아지면 정상적인 외부 서비스를 제공하고 사용자 경험을 보장하기 위해 인덱싱이 필요합니다.

색인 유형

색인은 데이터 구조이며 다양한 시나리오를 처리하기 위한 여러 구현이 있습니다. MySQL에서는 주로 Hash index와 B+Tree가 있습니다.

Hash Index

Hash 해시는 키-값 형태의 데이터 구조입니다. 구현은 일반적으로 배열 + 연결리스트 구조로 해시함수를 이용하여 배열 내 키의 위치를 ​​계산한 후, 해시 충돌이 발생하면 연결리스트(zipper 방식)를 통해 해결한다. 물론 해시 충돌을 해결하는 다른 방법도 있습니다. 해시의 데이터 구조는 매우 일반적으로 사용됩니다. 예를 들어 우리 시스템은 HashMap을 사용하여 핫스팟 데이터 캐시를 구축하며 액세스 효율성이 매우 좋습니다.

해시 구조는 키의 해시 값을 계산하여 배열에서의 위치를 ​​결정하여 먼저 데이터를 저장합니다. 충돌이 있는 경우 배열 위치에 연결된 목록이 작성됩니다. 여기에는 분명히 몇 가지 문제가 있습니다.

동일한 특성을 가진 키의 계산된 위치도 멀리 떨어져 있어 연속 쿼리가 비효율적일 수 있습니다. 즉, 범위 쿼리는 지원되지 않습니다.

해시 인덱스는 계산된 해시 값과 행 포인터를 저장하지만 특정 행 값을 저장하지는 않으므로 해시 인덱스를 통해 데이터를 쿼리하려면 두 가지 쿼리가 필요합니다(먼저 행의 위치를 ​​쿼리한 후 특정 데이터를 찾습니다)

해시 인덱스 쿼리 데이터의 전제는 해시 값을 계산하는 것인데, 이를 위해서는 키가 데이터 조각을 정확하게 가리킬 수 있는 키여야 하므로 like와 같은 일치 쿼리는 지원되지 않습니다.

그래서 우리가 알 수 있는 것은 해시 인덱스가 특정 데이터 행을 빠르게 선택하는 데 적합하다는 것입니다.

B+트리 구조

이름에서 알 수 있듯이 트리 구조는 대학 자료 구조 교과서에 필수입니다. 트리 구조는 여러 곳에서 사용되는 특히 중요한 데이터 구조입니다.

위에서 해시 인덱스는 범위 쿼리를 수행할 수 없다고 언급했습니다. 트리 구조에는 순서 쿼리에 편리한 구조인 이진 검색 트리도 있습니다. 이진 검색 트리의 구조에서는 아래와 같이 부모 노드의 값이 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작아야 합니다.

위에서 이진 트리 쿼리의 시간 복잡도 물론 숫자는 O(log(n))입니다. O(log(n))의 시간 복잡도를 보장하려면 이진 트리가 항상 균형을 유지하는지 확인해야 합니다.

MySQL 인덱스에도 트리 구조가 사용되지만 바이너리 트리는 아닙니다. 데이터베이스의 데이터는 궁극적으로 디스크에 저장되기 때문에 트리에 노드가 너무 많으면 노드 간 전송에 많은 시간이 걸립니다. MySQL 구현에서 우리는 효율성 향상이라는 목적을 달성하기 위해 동일한 노드에 더 많은 콘텐츠를 배치하고 동일한 노드의 작업을 메모리로 전송하여 외부 메모리의 노드 간 전송 횟수를 줄이는 것을 선택했습니다. 이것이 B+Tree입니다. B+Tree 구현에서는 3계층 트리 구조가 기본적으로 거의 모든 요구 사항을 충족할 수 있습니다.

관련 추천: "mysql 데이터베이스 지식 학습"

B-Tree

B+Tree를 이해하려면 먼저 B-Tree가 균형 트리이며 여기서 B는 다음을 의미한다는 것을 이해해야 합니다. B-Tree는 Binary가 아닌 Balance입니다.

다중 경로 균형 탐색 트리는 아래와 같습니다.

이것은 2-3 트리입니다. 즉, 각 노드는 2개의 값을 저장하고, 각 노드의 가지 수는 3개입니다. 위 그림을 보세요. 중간 구조는 데이터를 쿼리하는 데 매우 적합합니다. 각 노드의 왼쪽 하위 트리의 값은 현재 노드의 가장 작은 값보다 작고, 가운데 하위 트리의 값은 모두 현재 노드의 두 값 사이에 있고 오른쪽 하위 트리의 값은 모두 현재 노드의 최대값보다 큽니다.

예를 들어 값 24를 찾고자 하는 경우:

(1) 먼저 루트 노드에서 24가 루트 노드(15, 25) 사이에 있다고 판단하므로 왼쪽 및 오른쪽 하위 트리를 제외하고 검색은 다음과 같습니다. 중간부터.

(2) 그런 다음 중간 하위 트리의 루트 노드(18,22)를 찾아 비교한 결과 왼쪽 하위 트리와 중간 하위 트리를 제외한 노드의 최대값보다 24가 더 크다는 것을 알 수 있습니다.

(3) 올바른 하위 트리를 찾아 노드의 최대값이 정확히 24라고 판단하면 쿼리가 종료됩니다.

위 과정을 바탕으로 B-트리 검색을 요약하면 다음과 같습니다.

(1) 루트 노드부터 시작하여 노드 내 키워드(순서가 지정된) 시퀀스에 대해 이진 검색을 수행합니다.

(2) 맞으면 종료되고, 그렇지 않으면 쿼리 키워드 범위의 하위 노드를 입력합니다.

(3) 해당 자식 노드가 비어 있거나 이미 리프 노드가 될 때까지 위 과정을 반복합니다.

검색 성능은 키워드 세트 내에서 수행하는 것과 동일하다는 것을 알 수 있습니다. 이진 검색. 여기에서 B-Tree에는 아무런 문제가 없는 것처럼 보이지만 B-Tree의 각 노드는 인덱스 키와 그것이 나타내는 특정 행 데이터를 저장한다는 점에 유의해야 합니다. MySQL에서는 데이터베이스 로딩 데이터가 페이지 단위로 로딩되며, 각 페이지의 크기는 고정되어 있다(기본값은 16k). 각 노드가 모든 값을 저장하는 경우 페이지에 저장할 수 있는 노드가 거의 없으며 쿼리가 메모리에서 데이터를 여러 번 로드하여 성능이 저하될 수 있습니다.

B+Tree

B+Tree는 B-Tree의 변형으로, 외부 저장소 파일 인덱싱에 더 적합합니다.

둘의 가장 큰 차이점은 B-Tree의 각 노드는 모든 데이터를 저장하는 반면, B+Tree가 저장해야 할 데이터는 모두 리프 노드에 있고 순차 접근 포인터가 추가된다는 점입니다. 각 리프 노드에는 다음 인접 리프 노드를 가리키는 주소가 있습니다. 이 구조는 하나의 메모리 페이지에 더 많은 인덱스 노드를 저장할 수 있도록 보장하며 범위 쿼리에 더 적합합니다.

Index

스토리지 엔진이 인덱스 구현을 담당하기 때문에 다음에 설명하는 인덱스는 모두 MySQL의 InnoDB 엔진을 기반으로 합니다.

Clustered Index

클러스터링은 데이터 행과 인접한 키 값 클러스터가 함께 저장된다는 의미입니다. 일부 데이터베이스에서는 특정 인덱스를 클러스터형 인덱스로 선택할 수 있지만 InnoDB 구현에서는 기본 키 인덱스를 클러스터형 인덱스로 직접 지정합니다. 기본 키가 정의되지 않은 경우 InnoDB는 기본 키 인덱스를 대체하기 위해 null이 아닌 고유한 인덱스를 선택합니다. 이러한 인덱스가 정의되지 않은 경우 InnoDB는 기본 키를 클러스터형 인덱스(row_id)로 암시적으로 정의합니다.

클러스터형 인덱스의 예는 다음과 같습니다.

비클러스터형 인덱스#🎜🎜 ##🎜 🎜#InnoDB의 기본키 인덱스를 제외한 나머지 인덱스는 모두 논클러스터형 인덱스이므로 비기본키 인덱스라고도 합니다. 기본 키가 아닌 인덱스의 리프 노드에는 행의 값이 저장되지 않고 특정 행의 기본 키 값이 저장됩니다. 클러스터링의 정의가 충족되지 않습니다.

비클러스터형 인덱스의 예는 다음과 같습니다.

클러스터형 인덱스 및 비클러스터형 위의 두 인덱스 예제 다이어그램에서

의 시간 차이를 확인할 수 있습니다. 쿼리 시 기본 키 인덱스를 통해 쿼리하는 경우 데이터 행은 다음과 같습니다. 직접 문의하고 돌려받았습니다. 그러나 기본키가 아닌 인덱스를 통해 질의하는 경우에는 먼저 인덱스를 통해 기본키를 확인한 후, 획득한 기본키를 이용하여 기본키 인덱스에서 특정 행의 데이터를 찾는 과정이 필요하다. 획득한 기본키를 통해 기본키 인덱스로부터 데이터를 얻는 것을 테이블로 복귀(Return to table)라고 합니다.

테이블을 반환하는 과정에서 일반 인덱스를 통한 쿼리는 기본 키 인덱스를 통한 쿼리보다 한 단계 더 진행되며, 많은 경우 효율성이 상대적으로 낮습니다. 따라서 우리의 쿼리 과정에서 기본 키로만 데이터를 확인할 수 있는 경우에는 기본 키를 사용하여 직접 쿼리하는 것이 가장 좋습니다.

Covered index

위에서는 기본 키가 아닌 쿼리를 통해 테이블을 반환하는 과정을 설명했지만 모든 것이 아니라는 점에 유의해야 합니다. 모든 쿼리에는 테이블로 돌아가는 단계가 있습니다. 일반 인덱스의 경우 리프 노드는 기본 키 값을 저장합니다. 그렇다면 지금 필요한 데이터가 기본 키 값뿐이라면 어떻게 될까요? 일반 인덱스를 통해 기본키의 값을 얻은 후에는 기본키 인덱스에서 조회할 필요가 없으므로 테이블로 돌아가는 과정이 없다.

위의 예에서 비기본 키 인덱스에는 필요한 값이 이미 존재하므로 이 인덱스를 커버링 인덱스라고도 합니다. 커버링 인덱스는 고정된 구조가 아니며 단일 인덱스(한 필드에 대한 인덱스)일 수도 있고, 테이블 반환 프로세스를 수행할 필요 없이 쿼리 결과를 직접 제공할 수 있는 모든 것을 커버링 인덱스라고 할 수 있습니다.

기본키만으로는 데이터를 판별하는 것이 불가능한 경우가 많습니다. 일반 인덱스를 사용하는 것은 비효율성을 초래할 수 있으므로 인덱스를 포함하는 것도 일상적인 개발 프로세스에서 매우 일반적인 성능 최적화 방법입니다.

물론 인덱스 페이지를 덮는 것이 항상 좋은 것은 아닙니다. 예를 들어, 이제 인덱스 인덱스(a,b)를 만들었습니다. a와 b 두 필드를 사용하여 인덱스를 설정하면 ab 필드를 쿼리할 때 테이블이 반환되지 않는다는 장점이 있습니다. 그러나 b 필드로만 쿼리하는 경우에는 이 인덱스를 사용할 수 없습니다. 생성된 인덱스의 인덱스 항목은 인덱스 정의에 나타나는 필드 순서에 따라 정렬됩니다.

가장 왼쪽 접두사 원칙

인덱스 인덱스(a,b)가 있다고 가정하고 a, b를 통해 쿼리하면 이 Index를 적용할 수 있으며, a만 사용하여 쿼리하면 인덱스에 적용할 수 있지만, b만 사용하여 쿼리하면 인덱스에 적용할 수 없습니다. 이는 인덱스를 일치시킬 때 인덱스의 가장 왼쪽 n개 필드가 일치할 경우 인덱스를 적용할 수 있는 가장 왼쪽 접두사 원칙입니다.

가장 왼쪽 접두사 원칙이 존재하기 때문에 인덱스를 구축할 때 더 많은 사항을 고려해야 할 수도 있습니다.

먼저 인덱스는 데이터 구조라는 점을 분명히 해야 합니다. 인덱스를 만들 때 저장 공간이 소모되기 때문에 인덱스를 많이 생성할수록 좋다는 것이 아닙니다. 필요에 따라 최대한 줄여야 합니다.

가장 왼쪽 접두사 원칙이 존재하면 조인트 인덱스를 다중 인덱스로 사용할 수 있습니다. 물론 인덱스의 필드 순서를 설계하는 것이 전제입니다(사실 가장 왼쪽 접두사 원칙은 조인트에만 적용되는 것은 아닙니다. 문자열 인덱스도 사용되는 경우 문자열 인덱스의 가장 왼쪽 n 문자는 통합 인덱스의 가장 왼쪽 n 필드와 동일합니다.

예를 들어 index(a,b)의 경우, 이 인덱스를 사용하면 a에 대해 별도의 인덱스를 생성할 필요가 없기 때문에 공동 인덱스를 설계할 때 일반적으로 자주 사용되는 필드를 먼저 배치합니다.

그러면 판별률이 높은 필드를 먼저 배치합니다. 판별률은 해당 필드에 있는 값의 반복률입니다. 예를 들어 성별은 인덱스로 적합하지 않습니다. 구분이 높은 필드는 한 번 필터링하면 더 많은 행을 필터링할 수 있습니다.

그리고 필드의 크기도 고려해야 합니다. 인덱스도 공간을 차지해야 하므로 일반적으로 더 작은 필드가 선택됩니다.

참고 자료

MySQL 운영 및 유지 관리 내부 참고 자료: MySQL, Galera, Inception 핵심 원칙 및 모범 사례

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