MySQL 인덱스의 원리

MySQL 데이터베이스는 B-트리 인덱스, 해시 인덱스, 전체 텍스트 인덱스 등과 같은 다양한 인덱스를 지원합니다. 이 기사에서는 B-트리 인덱스에 중점을 둡니다. (권장: "mysql tutorial")

Index 원리 및 본질

MySQL 공식 설명: Index는 데이터를 빠르게 쿼리하기 위해 MySQL의 데이터 수집 효율성을 향상시키는 데이터 구조입니다. 인덱스는 특정 검색 알고리즘을 만족하는 데이터 구조로, 이러한 데이터 구조는 효율적인 데이터 검색을 위해 특정 방식으로 데이터를 가리킨다.

B+ 트리

MySQL은 일반적으로 B+ 트리를 인덱스 구조로 사용하는데, B+ 트리의 특징은 무엇인가요?

트리 차수가 n이면 각 노드 포인터의 상한은 2n+1입니다.

비리프 노드는 데이터를 저장하지 않으며, 포인터 인덱스만 리프 노드에 모든 데이터를 저장하지만 포인터는 저장하지 않습니다.

추가됨 고전적인 B+ 트리 순차 액세스 포인터의 기본인 각 리프 노드는 그림에 표시된 것처럼 다음 인접 리프 노드에 대한 포인터를 갖습니다. 주로 간격 액세스 성능을 향상시키기 위한 것입니다. 예를 들어 키가 20부터 50까지인 모든 데이터를 찾으려면 순차 액세스 경로에 따라 한 번에 모든 데이터 노드에 액세스하면 됩니다.

순차 액세스가 포함된 B+ 트리 다이어그램

지역성 원칙 및 디스크 미리 읽기

그렇다면 데이터베이스 시스템은 왜 일반적으로 레드-블랙 트리와 같은 다른 구조 대신 B+ 트리를 인덱스 구조로 사용합니까?

먼저 지역성의 원리와 디스크 미리 읽기의 개념을 소개하겠습니다.

일반적으로 인덱스 자체는 용량이 커서 메모리에 완전히 저장되지 않고 인덱스 파일 형태로 디스크에 저장됩니다. 따라서 데이터를 인덱스로 검색하는 동안 디스크 IO 연산이 발생하게 되며, 디스크 IO는 메모리 접근에 비해 매우 느리기 때문에 인덱스 구조는 디스크 IO 접근 횟수를 최소화해야 한다.

디스크 IO를 줄이기 위해 디스크는 특정 위치부터 데이터를 미리 읽고, 특정 길이의 데이터를 메모리로 미리 읽는 작업을 자주 수행하는데, 이것이 지역성의 원리입니다. 디스크 순차 읽기는 더 효율적이고 탐색 시간이 필요하지 않으므로 IO 효율성을 향상시킬 수 있습니다.

미리 읽기 길이는 일반적으로 페이지의 정수배이며, 메인 메모리와 디스크는 페이지 단위로 데이터를 교환합니다. 읽어야 할 데이터가 메모리에 없으면 시스템은 디스크 데이터를 읽으라는 요청을 디스크에 보내고 지속적으로 읽습니다. 여러 페이지의 데이터를 뒤로 이동하여 메모리에 로드합니다. 그런 다음 인터럽트가 반환되고 시스템이 계속 실행됩니다. 일반적인 데이터베이스 시스템을 설계할 때 B+ 트리 노드의 크기는 한 페이지로 설정되므로 각 노드의 로딩에는 한 개의 IO만 필요합니다.

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