사전 정렬을 통해 이진 검색과 같은 고효율 알고리즘을 사용하여 인덱스를 검색할 수 있습니다. 일반 순차 검색의 복잡도는 O(n)인 반면, 이진 검색의 복잡도는 O(log2n)입니다. n이 매우 클 경우 둘 사이의 효율성 차이는 엄청납니다.
Mysql은 인터넷에서 매우 인기 있는 데이터베이스입니다. 특히, Mysql 데이터의 저장 형식과 인덱스의 디자인이 전체 데이터 검색 성능을 결정합니다. MySQL.
인덱스의 기능은 데이터를 빠르게 검색하는 것이고, 빠른 검색의 핵심은 데이터 구조라는 것을 알고 있습니다. 다양한 데이터 구조를 선택함으로써 다양한 데이터를 신속하게 검색할 수 있습니다. 데이터베이스에는 많은 양의 데이터가 저장되어 있고 효율적인 인덱스를 사용하면 엄청난 시간을 절약할 수 있기 때문에 효율적인 검색 알고리즘이 매우 중요합니다. 예를 들어, 다음 데이터 테이블에서 Mysql이 인덱스 알고리즘을 구현하지 않은 경우 id=7인 데이터를 찾으려면 폭력적인 순차 탐색을 통해서만 id=7인 데이터를 찾을 수 있습니다. 7번 비교해야 합니다. 이 테이블에 1,000만 개의 데이터가 저장되어 있다면 id=1000W인 데이터를 검색하려면 1000W를 비교해야 합니다.
해시 테이블(Hash)
해시 테이블은 빠른 데이터 검색에 효과적인 도구입니다.
해시 알고리즘: 해시 알고리즘이라고도 하며 해시 함수를 통해 모든 값(키)을 고정 길이 키 주소로 변환하고 이 주소를 사용하여 특정 데이터에 대한 데이터 구조를 만듭니다.
이 데이터베이스 테이블 사용자를 고려하십시오. 테이블에 id=7인 데이터를 검색해야 합니다. SQL 구문은 다음과 같습니다.
select * from user where id=7;
해시 알고리즘이 먼저 계산하고 저장합니다. data with id=7 물리 주소 addr=hash(7)=4231이고, 4231로 매핑된 물리 주소는 0x77입니다. id=7로 저장된 데이터의 물리 주소입니다. 이 독립된 주소를 통해 만나보실 수 있습니다. 이는 해시 알고리즘이 데이터를 빠르게 검색하기 위해 사용하는 계산 프로세스입니다.
하지만 해시 알고리즘에는 데이터 충돌 문제가 있습니다. 즉, 해시 함수는 서로 다른 키에 대해 동일한 결과를 계산할 수 있습니다. 예를 들어 hash(7)은 hash(199)와 동일한 결과를 계산할 수 있지만 이는 키가 다릅니다. 동일한 결과로 매핑되는데, 이는 충돌 문제입니다. 충돌 문제를 해결하는 일반적인 방법은 링크드 리스트를 사용하여 충돌하는 데이터를 연결하는 체인 주소 방법입니다. 해시 값을 계산한 후에는 데이터 연결 리스트에서 해시 값이 충돌하는지 여부도 확인해야 하며, 충돌이 있으면 실제 키에 해당하는 데이터를 찾을 때까지 연결 리스트 끝까지 순회해야 합니다.
알고리즘 시간 복잡도 분석에서 해시 알고리즘 시간 복잡도는 O(1)로 검색 속도가 매우 빠릅니다. 예를 들어, id=7인 데이터를 검색할 때 해시 인덱스를 한 번만 계산하면 해당 데이터를 얻을 수 있으며 검색 속도가 매우 빠릅니다. 그러나 MySQL은 해싱을 기본 알고리즘으로 사용하지 않습니다. 이유는 무엇입니까?
데이터 검색의 일반적인 방법이 범위 검색이라는 점을 고려하면 다음 SQL 문과 같이:
select * from user where id \>3;
위 문에서 우리가 원하는 것은 id>3인 데이터를 찾는 것인데, 이는 매우 일반적인 방법입니다. 범위 검색. 해시 알고리즘으로 구현된 인덱스를 사용하는 경우 범위 검색은 어떻게 수행하나요? 간단한 아이디어는 모든 데이터를 한 번에 찾아 메모리에 로드한 다음 메모리에서 대상 범위 내의 데이터를 필터링하는 것입니다. 하지만 이 범위 검색 방법은 너무 번거롭고 전혀 효율적이지 않습니다.
그래서 해시 알고리즘을 사용하여 구현한 인덱스는 데이터를 빠르게 검색할 수는 있지만 데이터의 효율적인 범위 검색을 수행할 수 없습니다. 따라서 해시 인덱스는 Mysql의 기본 인덱스로 적합한 데이터 구조가 아닙니다.
이진 검색 트리(BST)
이진 검색 트리는 아래 그림과 같이 빠른 데이터 검색을 지원하는 데이터 구조입니다.
이진 검색 트리의 시간 복잡도는 O입니다. (lgn) 예를 들어, 위의 이진 트리 구조의 경우 id=7인 데이터를 검색하려면 세 번 계산하고 비교해야 합니다. 직접 순회 쿼리에 비해 검색 효율성 측면에서 보면 시간이 절반으로 절약됩니다. 고속 검색이 가능한 것 같습니다. 또한, 해시 인덱스가 제공할 수 없는 범위 검색 기능을 이진 트리 구조로 해결할 수 있을까?
답은 그렇습니다. 위 그림을 보세요. 이진 트리의 리프 노드는 왼쪽에서 오른쪽으로 오름차순으로 정렬되어 있습니다. id>5인 데이터를 찾아야 한다면 노드 6과 그 노드를 꺼내면 됩니다. 오른쪽 하위 트리. 범위 검색은 비교적 구현하기 쉽습니다.
그러나 일반적인 이진 검색 트리에는 치명적인 단점이 있습니다. 극단적인 경우 선형 연결 목록으로 변질되고 이진 검색도 순회 검색으로 변질되며 시간 복잡도가 O(N)으로 변질되고 검색 성능이 떨어집니다. 날카롭게. 예를 들어, 다음과 같은 상황에서는 이진 트리가 극도로 불균형하여 연결 리스트로 변질되어 검색 속도가 크게 저하됩니다. 이때 id=7인 데이터를 검색하는 데 필요한 계산 횟수는 7회로 늘어났습니다.
데이터베이스에서 데이터 자동 증가는 매우 일반적인 형태입니다. 예를 들어 테이블의 기본 키는 일반적으로 기본적으로 자동 증가입니다. 이진 트리와 같은 구조를 인덱스로 사용하면 위에서 소개한 불균형 상태로 인한 선형 검색 문제가 필연적으로 발생합니다. 따라서 단순 이진 검색 트리는 불균형으로 인해 검색 성능이 저하되는 문제가 있으며, Mysql의 기본 인덱스를 구현하는 데 직접 사용할 수 없습니다.
AVL 트리 및 레드-블랙 트리
이진 검색 트리에는 불균형 문제가 있으므로 학자들은 트리 노드의 자동 회전 및 조정을 통해 이진 검색 트리가 기본적으로 균형 잡힌 상태로 유지될 수 있다고 제안합니다. 검색 성능. 이 아이디어를 기반으로 자체 조정 평형 상태를 갖는 이진 트리에는 AVL 트리와 레드-블랙 트리가 포함됩니다.
먼저 레드-블랙 트리에 대해 간단히 소개하겠습니다. 이는 트리 모양을 자동으로 조정하는 트리 구조입니다. 예를 들어 이진 트리가 불균형 상태에 있으면 레드-블랙 트리가 자동으로 왼쪽으로 회전합니다. 올바른 노드와 노드는 트리의 모양을 조정하기 위해 색상을 변경하여 기본 평형 상태(시간 복잡도는 O(logn))를 유지하므로 검색 효율성이 크게 감소하지 않습니다. 예를 들어, 데이터 노드를 1부터 7까지 오름차순으로 삽입하면 일반적인 이진 검색 트리는 연결리스트로 퇴화되지만, 레드-블랙 트리는 그림과 같이 기본 균형을 유지하기 위해 지속적으로 트리의 모양을 조정합니다. 아래 그림에서. 아래 레드-블랙 트리에서 id=7을 검색할 때 비교되는 노드 수는 4개로 여전히 이진 트리의 좋은 검색 효율성을 유지하고 있다.
레드-블랙 트리는 평균 검색 효율이 좋고 극단적인 O(n) 상황이 없습니다. 그렇다면 레드-블랙 트리를 MySQL의 기본 인덱스 구현으로 사용할 수 있을까요? 사실, 레드-블랙 트리에도 몇 가지 문제가 있습니다. 다음 예를 살펴보세요.
레드-블랙 트리는 1~7개의 노드를 순차적으로 삽입하며, id=7을 검색할 때 계산해야 하는 노드 수는 4개입니다.
레드-블랙 트리는 1~16개의 노드를 순차적으로 삽입하는데, id=16을 찾기 위해 비교해야 하는 노드의 개수는 6번이다. 이 나무의 모양을 관찰해 보세요. 데이터를 순차적으로 삽입하면 나무의 모양이 항상 "오른쪽으로 기울어지는" 추세를 보였습니다. 맞습니까? 근본적으로 레드-블랙 트리는 이진 검색 트리를 완전히 해결하지 못합니다. 비록 이러한 "오른쪽으로 기울어지는" 추세가 선형 연결 목록으로 변질되는 이진 검색 트리보다 훨씬 덜 과장되어 있음에도 불구하고 기본 기본 키 자동 증가 작업은 다음과 같습니다. 데이터베이스의 기본 키는 일반적으로 수백만, 수천만 개입니다. 레드-블랙 트리에 이런 문제가 있으면 엄청난 양의 검색 성능도 소모하게 됩니다. 우리 데이터베이스는 이러한 무의미한 대기를 견딜 수 없습니다.
이제 더 엄격한 또 다른 자체 균형 이진 트리인 AVL 트리를 고려해 보세요. AVL 트리는 절대적으로 균형 잡힌 이진 트리이기 때문에 이진 트리의 모양을 조정하는 데 더 많은 성능을 소비합니다.
AVL 트리는 1~7개의 노드를 순차적으로 삽입하며, id=7을 찾기 위해 노드를 비교하는 횟수는 3회입니다.
AVL 트리는 1~16개의 노드를 순차적으로 삽입하는데, id=16으로 검색할 때 비교할 노드 수는 4개입니다. 검색 효율성 측면에서는 AVL 트리의 검색 속도가 레드-블랙 트리(AVL 트리는 4개 비교, 레드-블랙 트리는 6개 비교)보다 빠릅니다. 나무의 모양으로 볼 때 AVL 나무에는 레드-블랙 나무의 "오른쪽으로 기울어짐" 문제가 없습니다. 즉, 순차적 삽입을 많이 해도 쿼리 성능 저하로 이어지지 않아 레드-블랙 트리 문제가 근본적으로 해결된다.
AVL 트리의 장점을 요약하면
검색 성능(O(logn))이 뛰어나 극도로 비효율적인 검색 상황이 없습니다.
범위 검색 및 데이터 정렬을 구현할 수 있습니다.
AVL 트리는 데이터 검색을 위한 데이터 구조로 정말 좋은 것 같지만, AVL 트리는 MySQL 데이터베이스의 인덱스 데이터 구조에는 적합하지 않습니다. 왜냐하면 다음과 같은 문제를 고려하기 때문입니다.
데이터베이스의 병목 현상 쿼리 데이터는 디스크 IO입니다. AVL 트리를 사용하는 경우 각 트리 노드는 하나의 데이터만 저장하고 하나의 디스크 IO로 데이터를 메모리에 로드할 수 있습니다. id=7인 데이터를 쿼리하려면 디스크 IO를 세 번 수행해야 하는데, 시간이 많이 걸립니다. 따라서 데이터베이스 인덱스를 설계할 때 디스크 IO 수를 최대한 줄이는 방법을 먼저 고려해야 합니다.
디스크 IO의 한 가지 특징은 디스크에서 1B 데이터와 1KB 데이터를 읽는 데 걸리는 시간이 기본적으로 동일하다는 것입니다. 이 아이디어를 바탕으로 트리 노드에 최대한 많은 데이터를 저장할 수 있으며, 하나의 디스크 IO가 로드됩니다. 이것이 B-트리와 B+-트리의 설계 원리입니다.
B 트리
다음 B 트리는 노드당 최대 2개의 키를 저장하도록 제한됩니다. 노드에 키가 2개 이상 있으면 자동으로 분할됩니다. 예를 들어, 다음 B-트리는 7개의 데이터를 저장합니다. id=7인 데이터의 특정 위치를 확인하려면 두 개의 노드만 쿼리하면 됩니다. 즉, 두 개의 디스크 IO로 지정된 데이터를 쿼리할 수 있습니다. AVL 트리.
다음은 16개의 데이터를 저장하는 B-트리입니다. 마찬가지로 각 노드는 id=16인 데이터를 쿼리하고 비교해야 하므로 4개를 의미합니다. 디스크가 통과합니다. 쿼리 성능은 AVL 트리와 동일한 것 같습니다.
그러나 디스크 IO에서 데이터 한 개를 읽는 데 소요되는 시간이 기본적으로 데이터 100개를 읽는 것과 같다는 점을 고려하면 최적화 아이디어는 다음과 같이 바뀔 수 있습니다. 하나의 디스크 IO에. 이는 트리의 구조에 직접적으로 반영됩니다. 즉, 각 노드가 저장할 수 있는 키를 적절하게 늘릴 수 있습니다.
단일 노드로 제한된 키 수를 6으로 설정하면 7개의 데이터를 저장하는 B-트리는 ID=7인 데이터를 쿼리하는 데 2개의 디스크 IO가 필요합니다.
16개의 데이터를 저장하는 B-트리 id=7로 데이터를 쿼리하려면 2개의 디스크 IO가 필요합니다. AVL 트리에 비해 디스크 IO 수가 절반으로 줄어듭니다.
그래서 데이터베이스 인덱스 데이터 구조 선택 측면에서 B-tree는 매우 좋은 선택입니다. 정리하자면, B-트리를 데이터베이스 인덱스로 사용할 경우 다음과 같은 장점이 있습니다.
뛰어난 검색 속도, 시간 복잡도: B-트리의 검색 성능은 O(h*logn)과 같습니다. h는 트리 높이이고 n은 각각 노드 키워드 수입니다.
검색 속도를 높이려면 가능한 한 적은 디스크 IO가 필요합니다.
범위 검색을 지원할 수 있습니다.
B+트리
B트리와 B+트리의 차이점은 무엇인가요?
첫 번째, B 트리는 하나의 노드에 데이터를 저장하고, B+ 트리는 인덱스(주소)를 저장하므로 B 트리의 한 노드는 많은 데이터를 저장할 수 없지만 B+ 트리의 한 노드는 많은 인덱스를 저장할 수 있습니다. B+ 트리 리프 노드는 모든 데이터를 저장합니다.
둘째, B+ 트리의 리프 노드는 범위 검색을 용이하게 하기 위해 데이터 단계의 연결 리스트를 사용하여 직렬로 연결됩니다.
B 트리와 B+ 트리를 비교해보면 B+ 트리 노드는 단일 노드의 저장 용량이 제한되어 있을 때 많은 수의 인덱스를 저장할 수도 있음을 알 수 있습니다. 인덱스 전체를 B+로 만듭니다. 트리 높이가 줄어들어 디스크 IO가 줄어듭니다. 둘째, B+ 트리의 리프 노드는 실제 데이터가 저장되는 곳입니다. 리프 노드는 연결 리스트를 사용하여 연결됩니다. 연결 리스트 자체가 정렬되어 있어 데이터 범위에서 검색할 때 더 효율적입니다. 따라서 MySQL은 인덱싱을 위해 B+ 트리를 사용합니다. B+ 트리는 검색 효율성과 범위 검색에서 매우 좋은 성능을 발휘합니다.
Mysql 기반 데이터 엔진은 플러그인 형태로 설계되었습니다. 가장 일반적인 엔진은 Innodb 엔진과 Myisam 엔진입니다. MySQL 데이터 테이블의 기본 엔진입니다. 방금 B+ 트리가 Mysql 인덱스의 데이터 구조로 매우 적합하다고 분석했지만, 데이터와 인덱스를 구성하는 방법에도 약간의 설계가 필요했습니다. 서로 다른 디자인 개념으로 인해 각각 고유한 성능을 나타내는 Innodb와 Myisam이 등장하게 되었습니다.
MyISAM 데이터 조회 성능은 우수하지만 트랜잭션 처리를 지원하지 않습니다. Innodb의 가장 큰 특징은 ACID 호환 트랜잭션 기능을 지원하고, 행 수준 잠금을 지원한다는 점입니다. Mysql이 테이블을 생성할 때 엔진을 지정할 수 있습니다. 예를 들어 다음 예에서는 Myisam과 Innodb가 각각 user 테이블과 user2 테이블에 대한 데이터 엔진으로 지정됩니다.
이 두 명령을 실행하면 다음 파일이 시스템에 나타나 두 엔진의 데이터와 인덱스가 다르게 구성되었음을 나타냅니다.
테이블 생성 후 Innodb에서 생성된 파일은 다음과 같습니다.
frm: 테이블을 생성하는 문
idb: 테이블의 데이터 + 인덱스 파일
Myisam Created 테이블 다음에 생성된 파일에는
frm: 테이블을 생성하는 문
MYD: 테이블의 데이터 파일(myisam 데이터)
MYI: 테이블의 인덱스 파일(myisam index)
생성된 파일을 보면 두 엔진의 기본 데이터와 인덱스가 각각 다르게 구성되어 있는 것으로 보입니다. 사람은 비클러스터형 인덱스 방법이라고 하는 하나의 파일을 가지고 있습니다. Innodb 엔진은 데이터와 인덱스를 동일한 파일에 저장하며 이를 클러스터형 인덱스 방법이라고 합니다. 다음에서는 이 두 엔진이 B+ 트리 데이터 구조를 사용하여 기본 구현의 관점에서 엔진 구현을 구성하는 방법을 분석합니다.
MyISAM 엔진의 기본 구현(비클러스터형 인덱스 방법)
MyISAM은 비클러스터형 인덱스 방법을 사용합니다. 즉, 데이터와 인덱스가 두 개의 서로 다른 파일에 있습니다. MyISAM은 테이블을 생성할 때 기본 키를 KEY로 사용하여 기본 인덱스 B+ 트리를 생성합니다. 트리의 리프 노드는 해당 데이터의 물리적 주소를 저장합니다. 이 물리적 주소를 얻은 후에는 MyISAM 데이터 파일에서 특정 데이터 레코드를 직접 찾을 수 있습니다.
필드에 인덱스를 추가하면 해당 필드에 대한 인덱스 트리도 생성됩니다. 해당 필드에 대한 인덱스 트리의 리프 노드에도 해당 데이터의 물리적 주소가 기록됩니다. 그런 다음 이 물리적 주소를 사용하여 데이터 파일에서 특정 데이터 레코드를 찾습니다.
Innodb 엔진의 기본 구현(클러스터형 인덱스 방식)
InnoDB는 클러스터형 인덱스 방식이므로 데이터와 인덱스가 동일한 파일에 저장됩니다. 먼저 InnoDB는 아래 그림과 같이 기본 키 ID를 KEY로 기준으로 인덱스 B+ 트리를 생성하고 B+ 트리의 리프 노드에는 예를 들어 명령문을 실행할 때 기본 키 ID에 해당하는 데이터가 저장됩니다. select * from user_info where id=15, InnoDB 기본 키 ID 인덱스 B+ 트리를 쿼리하고 해당 user_name='Bob'을 찾습니다.
이것은 InnoDB가 테이블을 생성할 때 기본 키 ID 인덱스 트리를 자동으로 구축하는 경우입니다. 이것이 바로 Mysql이 테이블을 생성할 때 기본 키를 지정하도록 요구하는 이유입니다. 테이블의 필드에 인덱스를 추가할 때 InnoDB는 어떻게 인덱스 트리를 생성합니까? 예를 들어 user_name 필드에 인덱스를 추가하려는 경우 InnoDB는 user_name 인덱스 B+ 트리를 생성합니다. user_name의 KEY는 노드에 저장되고 리프 노드에 저장된 데이터는 기본 키 KEY입니다. 나뭇잎은 기본 키 KEY를 저장합니다! 기본 키 KEY를 얻은 후 InnoDB는 기본 키 인덱스 트리로 이동하여 user_name 인덱스 트리에서 방금 찾은 기본 키 KEY를 기반으로 해당 데이터를 찾습니다.
질문은 왜 InnoDB는 기본키 인덱스 트리의 리프 노드에만 특정 데이터를 저장하는데, 다른 인덱스 트리들은 특정 데이터를 저장하지 않고, 기본키를 먼저 찾을 필요가 없느냐는 것입니다. , 그리고 기본 키 인덱스 트리에서 해당 데이터를 찾아보면 어떨까요?
InnoDB는 저장 공간을 절약해야 하기 때문에 실제로는 매우 간단합니다. 테이블에 많은 인덱스가 있을 수 있습니다. InnoDB는 각 인덱스 필드에 대해 인덱스 트리를 생성합니다. 각 필드의 인덱스 트리에 특정 데이터가 저장되면 이 테이블의 인덱스 데이터 파일이 매우 커집니다(데이터가 극도로 중복됨). 디스크 공간 절약의 관점에서 보면 실제로 각 필드 인덱스 트리에 특정 데이터를 저장할 필요가 없습니다. 겉보기에 "불필요한" 단계를 통해 쿼리 성능을 저하시키는 대신 막대한 디스크 공간이 절약되는 것은 매우 가치 있는 일입니다.
InnoDB와 MyISAM의 기능을 비교할 때 MyISAM이 쿼리 성능이 더 좋다고 언급되었습니다. 그 이유는 위의 인덱스 파일 데이터 파일의 설계에서도 알 수 있습니다. MyISAM은 물리적인 데이터를 직접 찾은 후 데이터 레코드를 직접 찾을 수 있습니다. 그러나 InnoDB는 리프 노드를 쿼리한 후 특정 데이터를 찾기 위해 기본 키 인덱스 트리를 다시 쿼리해야 합니다. 이는 MyISAM이 한 단계로 데이터를 찾을 수 있지만 InnoDB는 두 단계가 필요하다는 것을 의미합니다. 물론 MyISAM의 쿼리 성능이 더 높습니다.
위 내용은 mysql 인덱스가 빠른 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
