Zhang San을 찾는 요구 사항이 있습니다. 이진 검색 트리를 사용하지 않으면 7번 검색하면 됩니다. 이진 검색 트리를 사용하면 원하는 값을 찾으려면 4번만 검색하면 됩니다.
위 내용에 따르면 이진 검색 트리를 사용하면 실제로 쿼리 수를 줄일 수 있지만 데이터베이스의 데이터가 1, 2, 3, 4, 5, 6, 7? 계속 사용하면 이진 검색 트리가 연결 목록이 됩니다. 따라서 7개를 찾으려면 7번 검색하고 테이블을 7번 스캔해야 합니다. 이는 인덱스를 생성하지 않는 것과 다르지 않으며, 이는 단점 중 하나이기도 합니다. 다음 그림은 예시입니다.

2)균형 이진 트리: AVL 트리라고도 하며 왼쪽과 오른쪽 하위 트리 사이의 높이 차이의 절대값은 1을 초과하지 않으며 왼쪽과 오른쪽 하위 트리는 모두 균형 이진 트리입니다. AVL 트리는 최초로 발명된 자체 균형 이진 검색 트리입니다. AVL 트리에서는 모든 노드의 두 하위 트리 사이의 최대 높이 차이가 1일 수 있으므로 높이 균형 트리라고도 합니다. 쿼리, 추가 및 삭제는 평균 및 최악의 경우 O(log n)입니다. 추가 및 삭제에는 트리 균형을 재조정하기 위해 하나 이상의 트리 회전이 필요할 수 있습니다.
이진 트리를 도입하는 목적은 이진 트리 검색의 효율성을 향상시켜 트리의 평균 검색 길이를 줄이는 것입니다. 이를 위해 각 이진 트리에 노드를 삽입할 때 트리 구조를 조정해야 합니다. 이진 트리 검색은 균형을 유지할 수 있으며, 트리 높이를 줄여 평균 트리 검색 길이를 줄일 수 있습니다.
균형 이진 트리의 특징은 다음과 같습니다.
1. 왼쪽 하위 트리와 오른쪽 하위 트리가 모두 AVL 트리입니다.
2. 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이는 1을 초과할 수 없습니다
예:
3)레드-블랙 트리: 레드-블랙 트리는 균형 잡힌 이진 트리보다 우수한 트리라고 이해할 수 있습니다. 레드-블랙 트리는 "완전한 균형"을 추구하지 않습니다. 균형 요구 사항을 충족하여 회전 요구 사항을 줄여 성능을 향상시킵니다. 또한, 설계상 불균형은 3회전 이내에 해결될 수 있습니다. 레드-블랙 트리에서는 알고리즘 시간 복잡도가 AVL과 동일하며 통계 성능으로 인해 AVL 트리가 더 높아집니다. 따라서 균형 이진 트리와 비교하면 레드-블랙 트리는 엄밀한 의미에서는 균형 이진 트리가 아니다. 레드-블랙 트리의 삽입 및 삭제 효율은 균형 이진 트리에 비해 상대적으로 낮다. 그러나 둘 사이의 쿼리 효율성 차이는 비교하면 기본적으로 무시할 수 있습니다. 레드-블랙 트리의 특징은 다음과 같습니다.
1.노드는 빨간색 또는 검은색입니다.
2.루트 노드는 검정색입니다.
3.각 빨간색 노드의 두 하위 노드는 검정색입니다. (레드 노드의 자식은 블랙 노드여야 합니다)
4.모든 노드에서 각 리프까지의 모든 경로에는 동일한 수의 블랙 노드가 포함됩니다.
따라서 레드-블랙 트리는 블랙 밸런스 트리이며 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 2를 초과하지 않습니다. 레드 노드의 부모 노드와 자식 노드는 블랙 노드만 될 수 있습니다.
예:

4)BTree(B-tree): 물론 위에서 언급한 레드-블랙 트리는 성능이 매우 높습니다. 위 그림을 예로 들면, 트리의 최대 높이는 4이고, 총 9개의 데이터가 있습니다. 그러나 Mysql 데이터베이스의 경우 수백만 개의 데이터, 수천만 개의 데이터가 있으며, 트리의 높이는 측정할 수 없습니다. 예를 들어, 수백 개의 데이터 1만 개는 데이터를 쿼리하는 데 30-50번의 디스크 IO 시간이 필요하거나 그보다 더 많은 시간이 필요하므로 분명히 Mysql 인덱스의 효율적인 쿼리 효율성을 충족할 수 없습니다. 따라서 트리의 높이를 제어하면 디스크 IO 요청 수가 크게 줄어듭니다. 높이가 4로 제어되면 데이터를 쿼리하는 데 4개의 디스크 IO만 필요합니다.
그런데 트리의 높이를 어떻게 제어할 수 있을까요? 레드-블랙 트리는 노드당 하나의 요소만 저장합니다. 각 노드가 여러 요소를 저장하면 어떻게 될까요? 이렇게 하면 모든 요소를 넣는 문제가 해결될 수 있습니다. 모두 하나의 노드에 배치하면 높이 값은 1이 됩니다. 더 빠르지 않나요? 이런 식으로 생각하는 것은 확실히 잘못된 것입니다.Mysql은 디스크 IO와 상호 작용할 때마다 크기 제한이 있습니다. Mysql은 각 노드의 크기를 16K로 제한합니다.Mysql의 노드 크기 제한을 확인하려는 학생은 다음 SQL을 실행할 수 있습니다.
'Innodb_page_size'와 같은 전역 상태를 표시합니다.
다음 그림은 BTree
BTree의 특성을 반영하는 예시로 사용됩니다.
1. 모든 인덱스 요소는 반복되지 않습니다.
2. 노드의 데이터 인덱스는 다음에서 증가합니다. 왼쪽에서 오른쪽으로
3. 리프 노드는 동일한 깊이에서 리프 노드의 포인터가 비어 있습니다
4. 리프 노드와 리프가 아닌 노드 모두 인덱스와 데이터를 저장합니다

5)B+ 트리: 위에서 언급했듯이 BTree는 트리의 높이를 제어하므로 Mysql의 인덱싱 요구 사항을 충족할 수 있습니다. 그러나 결국 Mysq 인덱스 구현은 BTree가 아니라 B+ 트리입니다. 변환 후 B+ 트리가 얻어졌는데, 이는 B+ 트리가 B 트리의 업그레이드 버전으로 이해될 수도 있습니다.
그림을 예로 들어보겠습니다.

이 그림에서 볼 수 있듯이 우리의 리프가 아닌 노드는 데이터가 아닌 인덱스만 저장하고 리프 노드는 포인터로 연결됩니다. B 트리의 리프 노드와 리프가 아닌 노드 모두 인덱스와 데이터를 저장하며 리프 노드의 포인터는 비어 있습니다. B+ 트리는 리프 노드가 아닌 노드에 더 많은 인덱스를 저장할 수 있도록 데이터를 리프 노드에 배치합니다. , 매번 디스크 IO에서 더 많은 인덱스를 얻을 수도 있습니다.
B+ 트리 기능은 다음과 같습니다.
1. 리프가 아닌 노드는 데이터를 저장하지 않으며 인덱스(중복) 및 하위 수준 포인터만 배치할 수 있습니다.
2. 리프 노드에는 모든 인덱스 필드와 데이터가 포함됩니다.
3 .Leaf 노드는 간격 액세스 성능을 향상하기 위해 이중 포인터로 연결됩니다.

바이두와 많은 블로그에 그려진 B+ 트리가 잘못되었으므로 함정을 피하십시오.
B+ 트리에 대한 Mysql의 공식 설명을 보고 싶으시면 확인해 보세요.
링크: Mysql 공식 홈페이지

4. 인덱스 분류

1. 인덱스의 저장 연관에 따른 분류: 크게 두 가지 카테고리로 나뉜다
1.) 클러스터 인덱스(clustered index): 리프 노드 완전한 데이터 레코드가 포함되어 있으므로 테이블에 반환할 필요가 없습니다.
2.) 비클러스터형 인덱스: 테이블을 반환하고 트리를 두 번 조회해야 하며 이는 성능에 영향을 미칩니다.

1.1)MySQL에 일반적으로 사용되는 두 가지 스토리지 엔진인 MyISAM과 InnoDB가 있다는 것은 누구나 알고 있지만 실제로 두 스토리지 엔진의 기본 데이터 스토리지 구조를 이해하셨나요?
설명을 위해 사진을 예로 들어보겠습니다.
test.myisam 테이블은 MyISAM 스토리지 엔진이고 actor 테이블은 InnoDB 스토리지 엔진입니다. MyISAM 스토리지 엔진에는 frm, MYD라는 세 개의 파일이 있는 것을 볼 수 있습니다. , MYI의 약어로는 테이블 구조를 저장하고, MYD-MYData는 데이터를 저장하며, MYI-MYIndex는 인덱스와 데이터를 별도로 저장합니다. 또한 테이블의 구조인 IBD 파일은 InnoDB 및 MyISAM과 다른 인덱스와 데이터를 저장합니다.
다음 그림은 MyISAM 스토리지 엔진의 기본 키 인덱스에 테이블 반환 작업이 필요함을 설명하기 위한 예로 사용됩니다(non-clustered index)
여기서 15는 기본 키 인덱스를 저장하고 0x07은 디스크 파일을 저장합니다. 우리와 같은 15행에 기록된 주소 포인터 15의 데이터를 찾으려면 먼저 기본 키 인덱스 트리를 통해 15에 해당하는 포인터를 찾은 다음 포인터를 찾은 다음 MyD 파일로 이동해야 합니다. 특정 데이터를 찾으려면 두 번째 검색이 필요합니다. 이 프로세스를 테이블 반환 작업이라고 합니다.
2.1)다음 그림은 InnoDB 스토리지 엔진 기본 키 인덱스에 테이블 반환 작업이 필요하지 않음을 설명하기 위한 예로 사용됩니다. (Clustered Index)
InnoDB 스토리지 엔진 하위 노드는 먼저 15번째 행에 인덱스를 저장하고, 15번째 이하의 열에는 해당 인덱스가 있는 행의 다른 모든 필드가 저장됩니다. 15개 중에서 트리를 두 번 검색하지 않고도 직접 찾을 수 있습니다.

2.기능별로 분류 : 크게 5가지로 구분
2.1기본키 인덱스 : InnoDB 기본키 인덱스는 테이블 반환 연산이 필요하지 않음
2.2일반 인덱스(보조 인덱스) : InnoDB 일반 인덱스에는 테이블 반환이 필요 작업, 보조 인덱스의 경우 기본적으로 기본 키와 공동으로 인덱스됩니다.
2.3고유 인덱스
2.4전체 텍스트 인덱스
2.5조인트 인덱스: 가장 왼쪽 접두사 원칙을 충족해야 함

3.2.2에서 일반 인덱스에는 테이블 반환 작업이 필요하다고 언급했는데, 없는 걸까요? 테이블을 반환해야 합니까? 일반 인덱스의 경우 대답은 '예'입니다. 특정 쿼리에서는 인덱스가 쿼리 요구 사항을 충족합니다. 이때 테이블로 돌아갈 필요가 없습니다.
Covering Index는 트리 검색 횟수를 줄이고 쿼리 성능을 크게 향상시킬 수 있으므로 Covering Index를 사용하는 것이 일반적인 성능optimization을 의미합니다.

예: 다음은 이 테이블의 초기화 문입니다.

mysql> create table T ( ID int primary key, k int NOT NULL DEFAULT 0, s varchar(16) NOT NULL DEFAULT '', index k(k)) engine=InnoDB; insert into T values(100,1, 'aa'),(200,2,'bb'), (300,3,'cc'),(500,5,'ee'),(600,6,'ff'),(700,7,'gg');

위 테이블 T에서 select * from T(여기서 k는 3과 5 사이)를 실행하면 몇 개의 트리 검색 작업을 수행해야 하며 몇 개의 행을 스캔하게 됩니까?
이제 이 SQL 쿼리문의 실행 흐름을 살펴보겠습니다. 아래 그림을보세요.

1.)k 인덱스 트리에서 레코드 k=3을 찾아 ID = 300;
2.)그런 다음 ID 인덱스 트리로 이동하여 ID=300;
에 해당하는 R3를 찾습니다. 3.)k 인덱스 트리에서 다음 값 k=5를 가져오고 ID=500을 얻습니다.
4.)ID 인덱스 트리로 돌아가서 ID=500에 해당하는 R4를 찾습니다.
5;k 인덱스 트리에서 가져오기 다음 값 k=6이 조건을 충족하지 않아 루프가 종료됩니다.

이 프로세스에서는 테이블 백이라고 부르는 기본 키 인덱스 트리 검색 프로세스로 돌아갑니다. 이 쿼리 프로세스는 k 인덱스 트리의 3개 레코드를 읽고(1, 3, 5단계) 테이블을 두 번(2, 4단계) 반환하는 것을 볼 수 있습니다.

이 예에서는 쿼리 결과에 필요한 데이터가 기본 키 인덱스에만 있으므로 테이블로 반환해야 합니다.

실행된 문장이 T에서 ID를 선택하는 경우(여기서 k는 3~5 사이),이때 ID 값만 확인하면 되며, ID 값은 이미 k 인덱스 트리에 있으므로 쿼리 결과는 다음과 같습니다. Table을 반납하지 않고 바로 제공 가능합니다. 즉, 이 쿼리에서 인덱스 k는 쿼리 요구 사항을 "covered"하며 이를 커버링 인덱스라고 합니다.

InnoDB에서는 테이블이 기본 키 순서에 따라 인덱스 형태로 저장됩니다. 이렇게 저장된 테이블을 인덱스 구성 테이블이라고 합니다. 그리고 앞서 언급했듯이 InnoDB는 B+ 트리 인덱스 모델을 사용하므로 데이터는 B+ 트리에 저장됩니다. 각 인덱스는 InnoDB의 B+ 트리에 해당합니다.

5. 인덱스 최적화

1. 위는 인덱스의 기본 개념, 분류 및 기본 구조 관련 지식을 설명합니다. 인덱스 최적화 관련 지식에 대해 이야기해 보겠습니다.

1.)결합된 인덱스 중 하나의 열에만 null 값이 포함되면 인덱스가 무효화됩니다
2.)해당 열의 계산된 인덱스가 무효화되고, 해당 범위 이후의 모든 인덱스가 무효화됩니다
3 .)쿼리 조건에 대해 함수를 사용하면 인덱스 오류가 발생합니다
4.)where 절에 != 또는 연산자를 사용하면 인덱스 오류가 발생합니다
5.)or를 사용하면 인덱스 오류가 발생합니다.
6.)퍼지 쿼리를 사용하면 '%a%' 대신 'a%'를 사용할 수도 있습니다.
7.)포함 인덱스를 사용하고 select * 문을 줄여보세요
8 .)가장 왼쪽 접두사 규칙을 충족합니다. 가장 왼쪽 열부터 시작하고 인덱스의 열을 건너뛰지 마세요
9.)문자열을 작은따옴표로 묶지 않으면 인덱스가 실패합니다

2. 인덱스 최적화에 대한 설명

다음과 같이 5가지 속성을 가진 새 직원 테이블을 생성합니다.

create table employees( id int primary key auto_increment comment '主键自增', name varchar(30) not null default '' comment'名字', age int not null default 1 comment '年龄', id_card varchar(40) not null default '' comment '身份证号', position varchar(40) not null default '' comment '位置' ); -- 创建联合索引 create index name_index on employees (name,age,position); -- 插入一条数据 insert into employees(name,age,id_card,position) values('张三',15, '201124199011035321','北京');

-- 下面以10条sql测试，注意建立的联合索引顺序是 name，age，position 1.explain select * from employees where age=15 and position='北京' and name='张三'; 2.explain select * from employees where name='张三' and age=15 and position='北京'; 3.explain select * from employees where age=15 and name='张三'; 4.explain select * from employees where position='北京' and name='张三'; 5.explain select * from employees where position='北京' and age=15; 6.explain select * from employees where position='北京' and age>15 and name='张三'; 7.explain select * from employees where position='北京'; 8.explain select * from employees where age=15; 9.explain select * from employees where name='张三'; 10.explain select * from employees where name != '张三';

以上10条sql有哪些是索引失效，有哪些是索引没有失效的呢？ 相信同学们已经有了答案，但是答案对不对呢，下面我们一起分析下。 首先说第1条，查询条件把3个索引全部用上了，但是索引的顺序有变化，由name，age，position变成 了age，position，name，想到这里肯定有很多同学给出的答案就是索引失效，但是事实证明这个结果 是错的，索引生效，肯定有很多同学疑惑，为什么呢，这条sql不满足最左原则法则呀，这就要涉及到sql 的执行流程了，这里博主简单说下，sql执行有1个优化器的过程，优化器的作用之一就是索引的选择优化， 所以优化器帮我们把索引的顺序变成正确的了，所以索引生效。 下面是第1条按照索引顺序sql和第2条没有按照索引顺序sql的执行结果。 执行结果入下图：可以发现全部生效。

첫 번째 sql 유형의 값은 ref이고 바이트는 288이며 ref에는 3개의 const가 있으며 모두 유효합니다.

두 번째 SQL 유형의 값은 ref이고 바이트는 288이며 ref에는 3개의 const가 있으며 모두 유효합니다.

想学习sql的执行流程的可以看博主的另一篇关于sql执行流程的文章哦。 有的同学有疑问了，那最左原则没有用了吗？ 答案：有用的。

现在我们说下第3、4、5条sql 第3条： explain select * from employees where age=15 and name='张三'; sql在执行的时候，优化器替我们把索引的顺序优化了，由 age -> name 变成 name -> age，这时 索引是生效的。 第4条： explain select * from employees where position='北京' and name='张三'; 索引顺序优化为name - > position,但是这时索引只有name索引生效，position没有生效，因为我 们建立的索引顺序是 name -> age - > position，你会发现跳过了age，索引本质也是一棵树，少 了一个节点，下面的索引当然不会生效了，这就没有满足最左原则法则。 第5条： explain select * from employees where position='北京' and age=15; 这就和第4条sql一样的道理了，第一个索引都不见了，后面的不可能生效。 执行结果如下：

세 번째 SQL 유형의 값은 ref이고 바이트는 126이며 ref에는 2개의 const가 있으며 모두 유효하다는 것을 알 수 있습니다.

4번째 SQL은 122바이트에 불과하고 참조에는 const가 1개만 있으며 이름 인덱스만 적용됩니다.

5조 sql 유형의 값은 all이고, bytes와 ref는 비어 있으며, 모두 유효하지 않습니다.

下面说第6条sql，剩下的sql都是和之前的sql一样的道理。 explain select * from employees where position='北京' and age>15 and name='张三'; 这条sql我们会发现，把索引字段全部使用了并且当作条件查询，不一样的是age是范围查找，优化器替我 们把索引顺序优化成 name -> age - > position ，按照我们索引优化第2条：在列上做计算索引失效，范围之后的索引全部失效，想必答案同学们都知道了。 执行结果如下：

6번째 sql은 126바이트에 불과하고 type의 값은 range, range search이며 이름과 나이 인덱스만 적용된다.

추천 학습:mysql 비디오 튜토리얼