[DB] 클러스터링 인덱스: 인덱스의 개념, MySQL에서 리프 노드에 메모리 주소가 아닌 Primary Key를 저장하는 이유

💋 인덱스란?

데이터베이스의 테이블에서 데이터를 검색하고 정렬하는 데 사용되는 구조

 

예를 들어, 한 대학교에서 학생들 테이블을 관리한다고 생각해 보자. 

column으로는 id(primary key), name, age, major 등등이 있다. 

이때 이름을 기반으로 한 검색이 매우 많다고 하자.

예를 들어 아래와 같은 검색이다.

 

SELECT * FROM STUDENTS WHERE NAME='깃짱';

 

이 경우에 매번 primary key로만 정렬된 테이블에서 '깃짱'이라는 이름을 한 학생을 찾으려면 테이블을 전부 뒤져봐야 한다. 

이렇게 값을 찾는 방식을 full scan이라고 한다. 대강 생각해봐도 상당히 비효율적이다.

 

이름 기반 검색이 자주 사용된다면, 이름을 가나다 순으로 만든 테이블을 별도로 두고 관리하면 어떨까? 

 

name	id (primary key)
기짱	134325
긱짱	4873876
긷짱	345621313
깃짱	546543

 

 

위 경우 데이터가 4개밖에 없지만, 정말정말 많은 상황에서도 이름으로 정렬이 되어 있으므로 더 빠르게 binary search를 통해서 찾을 수 있을 테고, 이름만 알게 된다면 id 값을 알게 되니 기존 테이블이 저장된 곳으로 가서 primary key 기반으로 빠르게 깃짱에 대한 칼럼을 찾을 수 있을 것이다. 

이렇게 별도의 테이블로 관리하는 칼럼을 인덱스라고 한다. 

 

인덱스를 사용하게 되면, 데이터의 저장(INSERT, UPDATE, DELETE) 성능을 희생하고, 그 대신 데이터의 읽기 속도를 높일 수 있다. 

 

💋 인덱스의 종류

✔ 프라이머리 인덱스

• 테이블의 primary key로 만들어진 인덱스
• 식별자
• NULL, 중복을 허용하지 않음

✔ 세컨더리 인덱스

• 프라이머리 키를 제외한 나머지 모든 인덱스
• 쿼리에서 자주 검색 조건으로 사용되는 column에 대해서 인덱스를 설정하면 secondary index가 된다. 

 

💋 인덱스 알고리즘

✔ B-Tree 알고리즘

• Balanced Tree
• 가장 일반적으로 사용되는 인덱스 알고리즘
• 그냥 일단 이걸 공부하면 됨.

✔ Hash 인덱스 알고리즘

• 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘
• 매우 빠른 검색을 지원함.
• 주로 메모리 기반의 데이터베이스에서 많이 사용함.

 

💋 B-Tree 인덱스

이 포스팅은 B-Tree 자료구조의 특징에 대해 설명하지 않는다. 

이 포스팅은 B-Tree 인덱스 내에서 데이터를 탐색, 추가, 변경, 삭제에 대한 내용을 포함하지 않는다.

해당 내용에 대해서 숙지하지 못했다면, 아래 링크를 참고해주면 좋을 것 같다.  

[자료구조] B-Tree의 개념, 파라미터, 데이터 삽입, 삭제 과정을 알아보자!

[자료구조] B-Tree 자료구조가 DB 인덱스에 사용되는 이유: secondary storage 접근과 block 단위의 저장

 

 

 

 

이미지 출처: https://mangkyu.tistory.com/286

 

 

💋 리프 노드의 Value에 저장하는 값 

이미지 출처: https://velog.io/@jsj3282/14.-B-Tree-%EC%9D%B8%EB%8D%B1%EC%8A%A4

 

• MySQL의 default 스토리지 엔진인 InnoDB의 인덱스를 통한 데이터 탐색 과정이다. 
• B-Tree 인덱스를 통해서 최하위 계층인 리프 노드까지 접근했다면, 우리는 리프 노드의 페이지에 있는 Value 값을 통해서 실제 데이터에 접근할 수 있게 된다. 
• 최상위에는 루트 노드가 존재하고, 최하위의 리프 노드에는 실제 데이터와 관련된 내용이 들어 있다. 
  • InnoDB 스토리지 엔진의 경우에는 Primary Key 값이 들어있다.
  • InnoDB를 제외한 다른 스토리지 엔진의 경우에는 실제 데이터가 저장된 물리적 주소값이 들어있다. 
  • 이 두 가지의 차이에 대해서 공부하기 위한 키워드는 클러스터링 인덱스이다. (아래에서 설명 예정임)

 

💋 클러스터링 인덱스 

✔ 클러스터링 인덱스란?

• 기본 키(primary key)에 대해서 형성되는 인덱스
  • PK 기반의 검색이 매우 빠름
• 테이블의 레코드를 비슷한 것(Primary Key 기준)들끼리 묶어서 저장하는 형태로 구현
• Primary Key 값에 의해 레코드의 물리적 저장 위치가 결정됨.
  • PK 값이 변경된다면, 그 레코드의 물리적인 저장 위치가 바뀌어야 함.
  • PK 값으로 클러스터링된 테이블은 PK 값에 대한 의존도가 상당히 크다. 
• 예) 학생들의 성적을 저장하는 테이블을 학생의 학번으로 클러스터링 인덱스를 생성한다면, 학번 순서대로 정렬되어 학생들의 성적 데이터가 저장된다. 이렇게 되면 원하는 학번의 성적을 찾을 때, 데이터베이스는 빠르게 해당 학번의 위치를 찾을 수 있어서 학번 기준으로의 조회 성능이 크게 향상된다. 
• MySQL에서 클러스터링 인덱스는 InnoDB 스토리지 엔진에서 제공(MyISAM은 pk에 대해서 자동으로 인덱스 생성 안함)

 

✔ 클러스터링 인덱스의 구조

 

이미지 출처: https://hoing.io/archives/5960

 

• 클러스터링 인덱스의 리프 노드에는 레코드의 모든 칼럼 값이 같이 저장되어 있음. 
• 즉, 클러스터링 테이블은 그 자체가 하나의 거대한 인덱스 구조로 관리되는 것

 

정리 Q&A (참고)

 

 

✔ 클러스터링 인덱스 적용 시 세컨더리 인덱스의 조회 

• 예) InnoDB 스토리지 엔진에서 이름 기준으로 인덱스를 생성해 이름 기준으로 조회하는 경우

이미지 출처: https://gywn.net/2015/01/innodb-adaptive-hash-index/

• 모든 세컨더리 인덱스는 해당 레코드가 저장된 주소가 아니라 PK 값을 저장하도록 구현됨. 
  • 만약에 실제 레코드가 저장된 주소를 가지고 있다면, 클러스터링 키 값이 변경될 때마다 데이터 레코드의 주소가 변경되고, 그때마다 해당 테이블의 모든 인덱스에 저장된 주소값을 변경해야 하는 일이 발생할텐데, 이런 오버헤드를 제거하기 위한 방법임. 

이미지 출처: https://mangkyu.tistory.com/286

 

✔ 클러스터링 인덱스 미적용 시 세컨더리 인덱스의 조회

• 예) MyISAM에서 이름 기준으로 세컨더리 인덱스를 생성해 이름 기준으로 조회하는 경우

이미지 출처: https://velog.io/@jsj3282/14.-B-Tree-%EC%9D%B8%EB%8D%B1%EC%8A%A4

• PK와 세컨더리 인덱스는 구조적으로 아무런 차이가 없음
• 데이터가 INSERT될 때 처음 저장된 공간에서 절대 이동하지 않음. 

 

✔ 클러스터링 인덱스의 장점과 단점

• 장점
  • PK 기준의 검색 성능이 매우 빠름. 
    • 특히 PK를 범위 검색하는 경우 매우 빠름
  • 테이블의 모든 세컨더리 인덱스가 PK를 가지고 있어서, 인덱스만으로 처리할 수 있는 경우가 많음. 
• 단점
  • 테이블의 모든 세컨더리 인덱스가 PK를 갖기 때문에 PK 값이 차지하는 메모리가 클 경우에 전체적으로 인덱스의 메모리 크기가 커짐. 
  • 세컨더리 인덱스를 통해서 검색할 때, PK 값을 알아낸 후 PK로 다시 한 번 검색해야 하므로 처리 성능이 느림.
  • INSERT 할 때, PK에 의해 레코드의 저장 위치가 결정되기 때문에 성능이 느림.
  • PK 키를 변경할 때, 레코드를 DELETE하고 INSERT하는 작업이 필요하기 때문에 성능이 느림. 

 

✔ 클러스터링 인덱스 사용 시 주의사항

• 클러스터링 인덱스인 PK의 메모리 크기 선정에 있어서 주의해야 함.
  • 클러스터링 인덱스가 될 PK는 모든 세컨더리 인덱스에 포함되기 때문에, PK가 차지하는 메모리 크기에 따라 세컨더리 인덱스의 메모리 크기는 기하급수적으로 증가함. 
• PK는 명시적으로 작성한다.
  • PK를 직접 명시해서 DDL을 작성하지 않더라도, InnoDB 스토리지 엔진에서는 내부적으로 일련번호 칼럼을 추가함.
  • 하지만, 이 내부적인 일련번호는 접근할 수 없으므로, 비즈니스 상 PK가 존재하지 않는다면, AUTO_INCREMENT를 통해 인조 식별자를 생성하는 것을 권장함. 

 

✔ (추가) 클러스터링 인덱스는 데이터를 PK 따라 배열처럼 연속적으로 저장할까?

InnoDB는 클러스터링 인덱스라서 pk 따라 물리적 주소가 결정되지만, 꼭 연속적인 것은 아닐 수도 있다.

배열처럼 정말 연속적으로 저장하려면 저장 공간을 무한으로 할당해 두어야 하는데, 이것은 현실적으로 불가능.

예를 들어, 별도의 테이블에 해당 pk의 데이터가 어디에 저장되어 있는지 관리하는 형태로 관리해서,

'pk 따라 데이터가 저장되는 물리적인 주소가 결정되는 것은 맞지만, 연속적이지는 않을 수 있다.'

 

 

 

💋 참고자료

• https://code-lab1.tistory.com/217
• Real MySQL 8.0 8장
• https://hoing.io/archives/5960
• https://www.youtube.com/watch?v=NkZ6r6z2pBg&t=21s
• https://www.youtube.com/watch?v=ywYdEls88Sw

 

 

도움이 되었다면, 공감/댓글을 달아주면 깃짱에게 큰 도움이 됩니다🌟