[MySQL] 인덱스

 

/* 인덱스란? */

인덱스(INDEX)란 색인, 목차라고 하며, 데이터 검색을 보다 효율적으로 할 수 있습니다. MySQL에서는 B-Tree를 개선시킨 B+Tree 인덱스 구조가 사용된다.

인덱스를 활용하면 데이터를 조회하는 SELECT 외에도 UPDATE, DELETE의 성능이 함께 향상된다. 

인덱스를 여러개 설정하면 각각의 인덱스는 별도의 B+Tree 구조를 갖는다.

 

/* B-Tree 구조 */

B-Tree는 자식 2개만은 가진 이진 트리 (Binary Tree)를 확장하여 N개의 자식을 가질 수 있도록 고안된 것이다. 

 

B-Tree는 최상위에 루트 노드, 중간에 브랜치 노드, 최하위에 리프 노드가 존재한다.

 

- B-Tree에서 모든 노드는 키와 포인터를 가진다. 내부 노드, 리프 노트 모두 키와 데이터에 대한 포인터를 가진다. 즉 데이터는 모든 노드에 저장된다.

- 리프 노드는 서로 연결되지 않는다 (순차검색 X)

- 탐색은 루트 노드에서 시작하여 리프 노드까지 내려가며 데이터가 어느 노드에만 있을 수 있으므로 탐색 과정이 복잡할 수 있다.

/* B+Tree 구조 */

 

내부 노드들은 키와 자식에 대한 포인터만을 가진다.

- 실제 데이터는 리프 노드에만 저장된다. -> 그래서 탐색은 루트 노드에서 시작하여 내부 노드를 통해 리프 노드까지 내려가서 찾는다. (탐색 과정이 단순하고 일관적이다)

- 리프 노드는 Double Linked List로 되어 있다. 순차접근O