[인덱스] B-Tree vs Hash, InnoDB vs MyISAM

대표적인 인덱스 알고리즘 : B-Tree vs Hash

• Hash 인덱스 알고리즘
  • 컬럼의 값으로 Hash값을 계산하여 인덱싱
  • → 그래서 전방(prefix)일치 등 값의 일부만 검색하거나 범위 검색 시엔 사용할 수 없음
  • 매우 빠른 검색을 지원
  • 메모리 기반 데이터베이스에서 주로 사용
• B-Tree 인덱스 알고리즘
  • 가장 일반적으로 사용되는 알고리즘
  • Hash와 달리 컬럼의 값을 변형하지 않고 원래의 값을 사용하여 인덱싱

 

B-Tree 인덱스의 구조

루트-브랜치-리프 노드로 구성된 B-Tree 인덱스

Root, Branch, Leaf 노드로 이루어져있음

• 루트 노드 : 최상위노드. 자식 노드 주소를 가지고있음
• 브랜치 노드 : 루트와 리프 사이의 중간 노드. 자식 노드 주소를 가지고 있음
• 리프 노드 : InnoDB와 MyISAM의 인덱스 리프노드가 갖는 값이 다름
  • MyISAM : 물리적인 데이터 주소(=ROWID, 레코드 주소)를 갖고있음
  • InnoDB : PK인덱스냐 세컨더리 인덱스냐에 따라 다름.
    • 세컨더리 인덱스 : PK를 갖고있음 (논리적인 주소)
    • PK 인덱스 : 데이터 파일. (페이지네이션에 유리)

 

MyISAM의 인덱스 리프노드는 레코드 주소를 가지고있어 이를 통해 데이터에 접근한다.

 

InnoDB의 세컨더리 인덱스 탐색 시, 리프노드의 PK를 찾아 다시 PK인덱스를 탐색한다.

얼핏보면 InnoDB는 탐색 단계가 하나 더 있어 성능 부하가 생길 것처럼 보이지만, PK는 이미 레코드 데이터를 포함하고 있기 때문에 데이터 파일의 물리적 위치까지 갈 필요가 없어진다. 이런 특성으로 InnoDB는 빠른 조회 성능을 보장한다.

('클러스터링 인덱스' 참고)

 

 

 

출처 : Real MySQL 8.0

https://product.kyobobook.co.kr/detail/S000001766482

Real MySQL 8.0 (1권) | 백은빈 - 교보문고