Mysql의 B+Tree 인덱스 원리를 깊이 이해

우선, 적절한 인덱스를 올바르게 생성하는 것이 데이터베이스 쿼리 성능을 향상시키는 기초입니다.

인덱스란 무엇인가요?

인덱스는 테이블의 데이터 행 검색 속도를 높이기 위해 만들어진 분산형 저장소 데이터 구조입니다.

지수는 어떻게 작동하나요?

위 그림과 같이 이제 sql 문이 있는 경우 select * from Teacher where id = 101, 인덱스가 없는 경우 이 레코드를 찾으려면 다음을 수행해야 합니다. ID = 101인 데이터와 일치하도록 전체 테이블 스캔. 인덱스가 있으면 디스크에 기록된 101에 해당하는 행의 주소를 인덱스를 통해 빠르게 찾을 수 있고, 주어진 주소를 기반으로 해당 행 데이터를 검색할 수 있습니다.

MYSQL 데이터베이스는 왜 B+TREE를 인덱스의 데이터 구조로 사용합니까?

데이터 검색 속도를 높이기 위해 가장 먼저 떠오르는 것은 이진 트리의 검색 시간 복잡도가 O(log2(n))에 도달할 수 있다는 것입니다. 이진 트리의 저장 구조를 살펴보겠습니다.

이진 트리 검색은 이진 검색과 동일합니다. 이진 검색은 쿼리의 효율성을 크게 향상시킬 수 있지만 문제가 있습니다. 이진 트리는 처음 삽입된 데이터를 루트 노드로 사용하므로 위 그림과 같이 오른쪽 부분만 보면 알 수 있습니다. 선형 연결리스트 구조이다. 현재 데이터에 1, 2, 3, 4, 5, 6만 포함되어 있으면 다음 상황이 발생합니다.

쿼리하려는 데이터가 6이면 모든 노드를 탐색하여 6을 찾아야 합니다. 즉, 이진 검색 트리는 전체 테이블 스캔과 동일하므로 인덱스 데이터 구조로 사용하기에 적합하지 않습니다.

이러한 추론을 바탕으로 선형 연결 리스트의 문제를 해결하기 위해 균형 이진 탐색 트리를 생각하기 쉽습니다. 균형 이진 트리가 어떻게 생겼는지 살펴보겠습니다.

균형 이진 검색 트리는 다음과 같이 정의됩니다. 노드의 하위 노드 간의 높이 차이는 1을 초과할 수 없습니다. 예를 들어 위 그림의 노드 20입니다. , 왼쪽 노드의 높이는 1이고 오른쪽 노드의 높이는 0입니다. 차이가 1이므로 위 그림은 정의를 위반하지 않으며 균형 이진 트리입니다. 이진 트리의 균형을 유지하는 방법에는 왼손, 오른손 및 기타 작업이 있습니다. 왼손 및 오른손 작업은 관련 지식을 직접 검색할 수 있습니다.

위 그림의 균형 이진 트리가 id 인덱스를 저장했다면 이제 id = 8인 데이터부터 시작하려면 먼저 루트 노드를 메모리에 로드하고 8과 10을 비교하여 8이 10보다 작은 것을 찾으면, 10개 하위 트리의 왼쪽을 계속 로드합니다. 5를 메모리에 로드하고 8을 5와 비교합니다. 같은 방식으로 노드 5의 오른쪽 하위 트리를 로드합니다. 이때 Hit가 발견되어 id가 8인 Index에 해당하는 데이터가 Load됩니다.

인덱스에 해당하는 데이터를 찾는 방법은 무엇인가요?

인덱스에 데이터를 저장하는 방법은 일반적으로 두 가지가 있습니다. 첫 번째는 id = 8인 행 데이터의 특정 데이터 내용을 모두 노드의 데이터 영역에 저장하는 것입니다. 또 다른 방법으로는 데이터 영역에는 실제로 데이터가 저장되어 있는 디스크 주소가 저장된다.

이 시점에서 균형 이진 트리는 선형 연결 목록의 문제를 해결합니다. 기본적으로 O(log2(n))에 도달하여 데이터 쿼리의 효율성은 괜찮은 것 같습니다. 그러면 MySQL은 왜 이러한 데이터 구조를 선택하지 않습니까? 이런 종류의 문제는 또 무엇입니까?

문제 1: 검색 효율성이 부족합니다. 일반적으로 트리 구조에서는 데이터의 깊이에 따라 검색 중 IO 수가 결정됩니다. 위 그림과 같이 id = 8인 데이터를 검색하려면 3개의 IO가 필요합니다. 데이터의 양이 수백만에 도달하면 트리의 높이가 무서울 것입니다.

질문 2: 쿼리가 불안정하지 않습니다. 쿼리된 데이터가 루트 노드에 있으면 IO가 하나만 필요합니다. 리프 노드이거나 분기 노드인 경우 여러 IO가 필요합니다.

문제 3: 노드에 저장되는 데이터 내용이 너무 적습니다. 운영 체제 및 디스크 데이터 교환 기능을 제대로 활용하지 못하며 디스크 IO의 미리 읽기 기능도 제대로 활용하지 못합니다. 운영체제와 디스크 사이의 데이터 교환은 페이지 단위이므로 1페이지 = 4K, 즉 운영체제는 IO마다 4K 데이터를 메모리에 로드하게 된다. 그러나 이진 트리의 각 노드 구조는 키워드 1개, 데이터 영역 1개, 하위 노드에 대한 참조 2개만 저장하므로 콘텐츠 4K를 채울 수 없습니다. 다행히 IO 작업을 열심히 했는데, 하나의 키워드만 로드되었습니다. 트리의 높이가 매우 높고, 검색된 키워드가 우연히 리프 노드나 가지 노드에 위치하게 되면 검색하는 데 많은 시간이 걸립니다. 키워드.

그러면 이 이진 트리 문제를 해결할 수 있는 구조가 있을까요?

다방향 균형 검색 트리가 있습니다: (균형 트리):

B 트리는 아래 그림과 같이 절대적으로 균형 잡힌 트리이며 모든 리프 노드의 높이가 동일합니다.

B Tree의 장점은 무엇이며, 일부 문제는 어떻게 해결하나요?

먼저 정의를 살펴보겠습니다. 위 그림은 2-3 트리를 보여줍니다(각 노드에는 2개의 키워드가 저장되어 있으며 3가지 방법이 있습니다). 그림에서 볼 수 있듯이 다중 방향 균형 검색 트리는 다중 포크를 의미합니다. 위에서 각 노드에 저장된 키워드 수와 경로 수의 관계는

키워드 수 = 경로 수 – 1입니다.

위 그림에서 id = 28인 데이터를 찾고 싶다고 가정해 보겠습니다. B TREE 검색 과정은 다음과 같습니다.

먼저 루트 노드를 메모리에 로드하고 두 개의 키워드 17과 35를 로드합니다. 판단 규칙은 다음과 같습니다. :

위 규칙에 따라 28에 도달한 후 28에 해당하는 데이터를 로드하고 28에 해당하는 데이터 영역을 찾습니다. 데이터 영역에는 특정 데이터 또는 데이터에 대한 포인터가 저장됩니다.

왜 이 구조가 균형 이진 트리 문제를 해결할 수 있나요?

운영 체제와 디스크의 상호 작용 특성을 잘 활용할 수 있습니다. 디스크의 미리 읽기 기능을 잘 활용하기 위해 MYSQL은 페이지 크기를 16K로 설정합니다. 하나의 노드(디스크 블록)를 16K로 변경합니다. 하나의 IO는 하나의 노드(16K)의 내용을 메모리에 로드합니다. 여기서는 키워드 타입이 int로 4바이트라고 가정하면, 각 키워드에 해당하는 데이터 영역도 4바이트라면 자식 노드의 참조를 고려하지 않고 위 그림의 각 노드는 대략 (16*1000)개의 데이터를 저장할 수 있다. / 8 = 2000개의 키워드, 그러면 총 2001개의 방법이 있습니다. 3단계 높이의 이진 트리의 경우 최대 7개의 키워드를 저장할 수 있지만, 2001개의 경로를 가진 이 B-트리의 경우 3단계 높이에서 검색할 수 있는 키워드 수가 훨씬 많습니다. 이진 트리.

B TREE가 트리의 균형을 확보하는 과정에서 키워드가 바뀔 때마다 구조에 큰 변화가 생기기 때문에 이 과정은 특히 시간이 많이 걸리므로 인덱스를 생성할 때 대신에 적합한 인덱스를 생성해야 합니다. 모든 필드는 인덱싱됩니다. 중복 인덱스를 생성하면 데이터를 추가, 삭제, 수정할 때 성능 소모만 늘어납니다.

B-tree가 문제를 매우 잘 해결했는데 왜 MYSQL은 여전히 ​​B+TREE를 사용하나요?

먼저 B+TREE가 어떻게 생겼는지 살펴보겠습니다. B+TREE는 B+ 트리 종에서 B 트리 종의 경로 수와 키워드 수 사이의 관계가 더 이상 유효하지 않습니다. B+TREE에서 데이터 검색 규칙은 왼쪽 닫힌 간격을 사용하며 아래 그림과 같이 경로 수와 키 수의 관계는 1:1입니다.

위 그림이 ID로 indexed되며, 검색 id = 1인 경우 데이터에 대한 검색 규칙은 다음과 같습니다.

위 규칙에 따라 데이터는 최종적으로 리프 노드에 히트되고, 실제 데이터는 다음과 같습니다. 리프 노드에 있는 노드 1의 데이터 영역.

B TREE와 B+TREE의 차이점은 무엇인가요?

1. B+TREE 키워드 검색은 왼쪽 닫힌 간격을 사용합니다. 왼쪽 닫힌 간격을 사용하는 이유는 mysql의 원래 설계 의도이기도 한 자동 증가 ID를 가장 잘 지원해야 하기 때문입니다. 즉, id = 1이 나오면 리프 노드에서 1이 발견될 때까지 검색이 계속됩니다.

2.B+TREE 루트 노드와 가지 노드에는 데이터 영역이 없으며, 키워드에 해당하는 데이터는 리프 노드에만 저장됩니다. 즉, 리프 노드의 키워드 데이터 영역에만 실제 데이터 내용이나 내용의 주소가 저장됩니다. B 트리 종에서는 루트 노드에 맞으면 데이터가 직접 반환됩니다. 그리고 B+TREE에서 리프 노드는 하위 노드에 대한 참조를 저장하지 않습니다.

3. B+TREE 리프 노드는 순차적으로 배열되며, 인접한 노드는 순차적 참조 관계를 갖습니다. 위 그림과 같이 리프 노드는 포인터로 연결됩니다.

MYSQL이 결국 B+TREE를 선택한 이유는 무엇인가요?

1. B TREE는 B TREE가 해결할 수 있는 문제, B+TREE도 해결할 수 있는 변형입니다. (트리의 높이를 줄이고 노드에 저장되는 데이터의 양을 늘림)

2. B+TREE는 데이터베이스를 검색하고 테이블 검색 기능이 더 강력합니다. 인덱스를 기반으로 데이터 테이블을 검색하려는 경우 B TREE를 검색하려면 전체 트리를 순회해야 하지만 B+TREE는 모든 리프 노드만 순회하면 됩니다. 리프 노드) 사이에 참조가 있습니다.

3. B+TREE는 더 강력한 디스크 읽기 및 쓰기 기능을 가지고 있습니다. 루트 노드와 지원 노드는 데이터 영역을 저장하지 않습니다. 모든 루트 노드와 지원 노드가 동일한 크기일 때 B TREE보다 더 많은 키워드를 저장할 수 있습니다. 리프 노드는 하위 노드 참조를 저장하지 않습니다. 따라서 B+TREE는 B TREE보다 디스크에 로드된 키워드를 더 많이 읽고 씁니다.

4. B+TREE는 정렬 능력이 더 강합니다. 위 그림에서 볼 수 있듯이 B+TREE는 당연히 정렬 기능을 가지고 있습니다.

5. B+TREE 쿼리 효율성이 더 안정적입니다. 데이터를 쿼리할 때마다 IO 쿼리 수가 안정적이어야 합니다. 물론, 이에 대한 모든 사람의 이해는 다릅니다. B TREE에서는 루트 노드에 도달하면 직접 반환되므로 실제로 더 효율적입니다.

MYSQL B+TREE

의 구체적인 구현 형태

여기서 주요 설명은 서로 다른 B+TREE 인덱스 구조를 기반으로 하는 MYSQL의 두 가지 스토리지 엔진(MYISAM 및 INNODB)의 구현입니다. 먼저 MYSQL이 데이터를 저장하는 폴더를 찾고 mysql이 데이터를 저장하는 방법을 확인하세요.

다음을 입력하세요. 모든 데이터베이스는 이 디렉터리에 저장되며 특정 데이터베이스 디렉터리를 입력합니다. 여기에는 다양한 데이터 저장 엔진이 있습니다. 그림과 같이 MYISAM과 innodb에 대해 설명합니다.

MYISAM 저장 엔진 인덱스:

그림에서 볼 수 있듯이 MYISAM 저장 엔진이 사용됩니다. 데이터베이스 데이터를 저장하기 위한 파일은 총 3개입니다:

Frm, 테이블 정의 파일. MYD: 데이터 파일, 모든 데이터가 이 파일에 저장됩니다. MYI: 인덱스 파일.

MYISAM 스토리지 엔진에서 데이터와 인덱스의 관계는 다음과 같습니다.

데이터를 찾는 방법은 무엇인가요? id = 101 인 데이터를 조회하려면 먼저 MYI 인덱스 파일에 따라 id = 101 인 노드를 찾고(위 그림의 왼쪽 참조), 해당 데이터를 통해 실제로 데이터를 저장하는 디스크 주소를 구합니다. 그런 다음 이 주소를 사용하여 MYD 데이터 파일에서 데이터를 가져옵니다. (위 그림의 오른쪽과 같이) 해당 레코드를 로드합니다.

여러 개의 인덱스가 있는 경우 표현은 다음과 같습니다.

그래서 MYISAM 스토리지 엔진에서는 기본 키 인덱스와 보조 인덱스가 동일한 레벨에 있고 기본 키 인덱스와 보조 인덱스의 구분이 없습니다.

Innodb 스토리지 엔진:

먼저 클러스터형 인덱스의 개념을 살펴보겠습니다. 클러스터형 인덱스는 다음과 같이 정의됩니다. 데이터베이스 테이블 행에 있는 데이터의 물리적 순서는 키의 논리적 순서와 동일합니다. 가치.

Innodb는 기본 키를 인덱스로 사용하여 데이터 저장소를 집계하고 구성합니다. Innodb가 데이터를 구성하는 방법을 살펴보겠습니다.

Innodb에는 FRM 파일, 즉 테이블 정의 파일과 Ibd 파일 두 개만 있습니다. 특별히 데이터를 저장하는 파일은 없습니다. 데이터는 기본 키를 사용해 집계되어 저장되며, 실제 데이터는 리프 노드에 저장됩니다. innodb의 원래 설계 의도는 기본 키가 가장 중요한 인덱스라는 것입니다. 아래 그림과 같이

위 그림과 같이 리프 노드의 데이터 영역은 실제 데이터를 저장하고 있으며, 인덱스를 통해 조회할 때 리프 노드에 도달하면 행 데이터를 얻을 수 있습니다. 리프 노드에서 직접 가져옵니다. mysql5.5 버전 이전에는 MYISAM 엔진을 사용하였고, 5.5 이후에는 innodb 엔진을 사용하였다.

innodb에서 보조 인덱스의 형식은 아래 그림과 같죠?

위에 표시된 것처럼 기본 키 인덱스의 리프 노드에는 실제 데이터가 저장됩니다. 보조 인덱스 리프 노드의 데이터 영역에는 기본 키 인덱스 키의 값이 저장됩니다. 검색 프로세스는 다음과 같습니다. 이름 = 7인 데이터를 쿼리하려면 먼저 보조 인덱스를 쿼리하고 마지막으로 기본 키 ID = 101을 찾은 다음 기본 키 인덱스에서 ID 101인 데이터를 검색하여 마지막으로 가져옵니다. 기본 키 인덱스 데이터의 리프 노드에서 가져온 실제 데이터입니다. 따라서 보조 인덱스를 통한 검색에는 인덱스 검색이 두 번 필요합니다.

Innodb와 MYISAM의 차이점을 아래와 같이 그림으로 표현해 보세요:

인덱스 생성을 위한 몇 가지 원칙:

1. 이산형 컬럼:

이산형 계산 공식: count(distinct col ):count(col), 이산 유형이 높을수록 선택 유형이 더 좋습니다.

다음 표의 각 필드에 대해 가장 좋은 이산 유형을 가진 열은 무엇입니까?

위 그림에서 성별을 사용하여 인덱스를 생성하는 경우 이산 유형의 이름이 가장 좋습니다.

왜 이산형이라고 하나요? 높을수록 선택형이 좋은건가요?

아래와 같이 Sex에 대한 인덱스가 생성되면 인덱스 구조는 다음과 같습니다.

이 때 sex = 1의 데이터를 검색하면 루트 노드로 판단할 때 결과는 다음과 같습니다. 왼쪽 하위 트리에 질의하는 것이지만, 왼쪽 하위 트리의 두 번째 레이어를 판단할 때 왼쪽과 오른쪽 가지 모두 조건을 만족하기 때문에 어느 가지를 계속 검색할지, 아니면 두 가지를 동시에 검색할지 결정하기 어렵다. 시간.

2. 최좌측 일치 원칙

인덱스의 키워드 비교 시 비교는 왼쪽에서 오른쪽으로 이루어져야 하며 건너뛸 수 없습니다. 앞서 설명한 id는 모두 int 데이터입니다. id가 문자열인 경우 아래와 같습니다.

일치 시 문자열은 abc가 97 98 99가 되는 등 ascll 코드로 변환된 다음 왼쪽에서 오른쪽으로 문자별로 비교됩니다. 따라서 SQL 쿼리에서 %a와 같이 사용하면 %는 전체 일치를 의미하므로 인덱스가 유효하지 않습니다. 전체 일치가 있으면 인덱스가 필요하지 않습니다. 전체 테이블을 직접 스캔하는 것이 좋습니다.

3. 최소 공간 원칙

앞서 언급했듯이 키워드가 차지하는 공간이 작을수록 각 노드에 더 많은 키워드가 저장되고, 매번 더 많은 키워드가 메모리에 로드될수록 검색 효율성이 높아집니다.

조인트 인덱스:

단일 컬럼 인덱스: 노드의 키워드 [이름]

조인트 인덱스: 노드의 키워드 [이름, 전화번호]

단일 컬럼 인덱스는 특별한 조인트 인덱스로 간주할 수 있으며, 조인트 인덱스의 비교 또한 가장 왼쪽 일치 원칙을 기반으로 합니다.

공동 인덱스 열 선택 원칙:

(1) 자주 사용되는 열 우선 순위(가장 왼쪽 일치 원칙)

(2) 이산성이 높은 열 우선 순위(고 이산성 원칙)

(3) 작은 너비 열 우선 순위, (최소 공백 원칙)

다음은 자주 접하는 문제의 간단한 예입니다.

예를 들어 일반적으로 사용되는 sql 쿼리는 다음과 같습니다.

Select * from users where name = ? Select * from users where name = ?

Select * from users where name = ? and pahoneNum = ?

为了加快检索速度，为上面的查询sql创建索引如下：

Create index idx_name on users(name)

Create index idx_name_phoneNum on users(name, phoneNum)

在上面解决方案中，根据最左匹配原则，idx_name为冗余索引， where name = ?同样可以利用索引idx_name_phoneNum进行检索。冗余索引会增减维护B+TREE平衡时的性能消耗，并且占用磁盘空间。

覆盖索引：

如果查询的列，通过索引项的信息可直接返回，则该索引称之为查询SQL的覆盖索引。覆盖索引可以提高查询的效率。

下面通过例子说明覆盖索引。

表：teacher

索引：PK（id）， key（name， phoneNum）， unique（teacherNo）

下面哪些sql使用到了覆盖索引？

Select teacherNo from teacher where teacherNo = ?：使用到了，检索到teacherNo 时候，可以直接将索引中的teacherNo 值返回，不需要进入数据区。

Select id，teacherNo from teacher where teacherNo = ?：使用到了，辅助索引的叶子节点保存了主索引的值，所以检索到辅助索引的叶子节点的时候就可以之间返回id。

Select name，phoneNum from teacher where teacherNo = ?：没有用到

Select phoneNum from teacher where name = ?

name = ? 및 pahoneNum = ?인 사용자에서 *를 선택합니다.

검색 속도를 높이려면 다음과 같이 위 쿼리 SQL에 대한 인덱스를 생성합니다.

사용자에 대한 인덱스 idx_name을 생성합니다. (name)

사용자(name,phoneNum)에 대한 인덱스 idx_name_phoneNum 생성

위 솔루션에서 가장 왼쪽 일치 원칙에 따라 idx_name은 중복 인덱스입니다. 여기서 name = ? Index idx_name_phoneNum을 사용하여 검색할 수도 있습니다. 중복 인덱스는 B+TREE 균형을 유지하고 디스크 공간을 차지하는 성능 소비를 늘리거나 줄입니다.

커버링 인덱스:

인덱스 항목의 정보를 통해 쿼리 열을 직접 반환할 수 있는 경우 해당 인덱스를 SQL 쿼리를 위한 커버링 인덱스라고 합니다. 포함 인덱스는 쿼리 효율성을 향상시킬 수 있습니다.

다음은 커버링 인덱스를 예시를 통해 설명합니다.

Table: Teacher

Index: PK(id), key(name,phoneNum),unique(teacherNo)

다음 중 포함 인덱스를 사용하는 SQL은 무엇입니까?

TeacherNo = ?인 Teacher에서 TeacherNo 선택: 사용하면 TeacherNo를 검색할 때 데이터 영역에 입력하지 않고도 인덱스의 TeacherNo 값을 직접 반환할 수 있습니다.

Select id, TeacherNo from Teacher where TeacherNo = ?: 사용 시 보조 인덱스의 리프 노드는 기본 인덱스의 값을 저장하므로 보조 인덱스의 리프 노드를 검색할 때, 아이디를 돌려받을 수 있습니다.

교사번호 = ?인 교사의 이름, 전화번호 선택: 사용되지 않음 🎜🎜이름 = ?인 교사의 전화번호 선택, 사용됨. 🎜🎜커버링 인덱스를 알고 나면 SQL에서 select *를 최대한 사용하지 않고 쿼리할 특정 필드를 지정해야 하는 이유 중 하나는 커버링 인덱스를 사용할 때 데이터 영역을 입력해야 합니다. 데이터를 직접 반환할 수 있어 쿼리 효율성이 향상됩니다. 🎜🎜이전 연구를 통해 다음과 같은 결론을 쉽게 이해할 수 있습니다. 🎜🎜1. 인덱스 열의 데이터 길이는 비즈니스 요구 사항을 충족하면 최대한 짧아도 됩니다. 🎜🎜2. 테이블에 인덱스가 많을수록 좋습니다. 🎜🎜3. Where 조건에서는 like 9%, like %9%, like%9 세 가지 방법은 인덱스를 사용하지 않습니다. 후자의 두 가지 방법은 인덱스에 유효하지 않습니다. 처음 9%는 불확실하며 컬럼의 이산형에 따라 다르다. 결론적으로 이산형 상황이 특히 나쁘다고 판단되면 쿼리 옵티마이저는 인덱스 쿼리 성능이 더 나쁘다고 느끼지만 그렇지는 않다. 전체 테이블 스캔만큼 좋습니다. 🎜🎜4. Where 조건에서는 NOT IN에 인덱스를 사용할 수 없습니다. 🎜🎜5. 지정된 쿼리를 더 자주 사용하고, 원하는 열만 반환하고, select * less를 사용하세요. 🎜🎜6. 쿼리 조건에 함수를 사용하면 인덱스가 유효하지 않게 됩니다. 이는 열의 이산형과 관련이 있으므로 함수를 사용하면 함수가 확실하지 않습니다. 🎜🎜7. 공동 인덱스에서는 인덱스의 가장 왼쪽 열부터 검색을 시작하지 않으면 해당 인덱스를 사용할 수 없습니다. 🎜🎜8. 결합 인덱스의 가장 왼쪽 열과 범위가 다른 열을 정확하게 일치시키려면 인덱스를 사용할 수 있습니다. 🎜🎜9. 결합 인덱스에서 쿼리에 특정 열의 범위 쿼리가 있는 경우 그 오른쪽에 있는 모든 열은 인덱스를 사용할 수 없습니다. 🎜🎜추천 Mysql 튜토리얼 "🎜Mysql 튜토리얼🎜"🎜

위 내용은 Mysql의 B+Tree 인덱스 원리를 깊이 이해의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!