study MySQL 인덱스 랜덤 I/O 순차 I/O B-Tree

인덱스란?

Balanced-Tree

책너두 6기 21일차

백은빈, 이성욱의 Real MySQL8.0 1권 p.216 ~ p.227

내용정리

08 인덱스

8.1.2 랜덤 I/O와 순차 I/O

  • 랜덤 I/O는 HDD의 플래터(원판)를 돌려서 읽어야 할 데이터가 저장된 위치로 디스크 헤더를 이동시킨 다음 데이터를 읽는 것을 의미
  • 사실 순차 I/O도 이 작업 과정은 같다.
  • 순차 I/O는 3개의 페이지(3X16KB)를 디스크에 기록하기 위해 1번 시스템 콜을 요청 => 디스크의 헤드 1번 이동
  • 랜덤 I/O는 3개의 페이지를 디스크에 기록하기 위해 3번 시스템 콜을 요청 => 디스크의 헤드 3번 이동

  • 디스크에 데이터를 쓰고 익는데 걸리는 시간은 순차 I/O가 랜덤 I/O보다 3배 빠르다.

  • 디스크의 성능은 디스크의 헤더의 위치 이동 없이 얼마나 많은 데이터를 한 번에 기록하느냐에 의해 결정

8.2 인덱스란?

  • 칼럼(또는 칼럼들)의 갑소가 해당 레코드가 저장된 주소를 키와 값의 쌍(key - Value pair)으로 삼아 인덱스를 만들어 두는 것
  • 인덱스는 칼럼의 값을 주어진 순서로 미리 정렬해서 보관한다.
  • 인덱스는 항상 정렬된 상태를 유지한다.
  • 데이터 파일은 저장된 순서대로 별도의 정렬 없이 그대로 저장해 둔다.
  • DBMS에서 인덱스는 데이터의 저장(insert, update, delete) 성능을 희생하고 그 대신 데이터의 읽기 속도를 높이는 기능이다.
  • 이 책에서 키(Key)라는 말과 인덱스(Index)는 같은 의미로 사용된다.
  • 인덱스를 역할로 구분할 수 있다.
    • 프라이머리 키(Primary key) : 그 레코드를 대표하는 칼럼의 값으로 만들어진 인덱스. 이 칼럼은 식별자라고도 불린다. NULL, 중복을 허용하지 않는다.
    • 세컨더리 인덱스(Secondary index) : 대체 키라고도 한다.
  • 데이터 저장 방식(알고리즘)으로 분류할 수도 있다.
    • B-Tree 알고리즘 : 가장 일반적으로 사용. 칼럼의 값을 변형하지 않고 원래의 값을 이용해 인덱싱. R-Tree도 이를 응용한 것.
    • Hash 인덱스 알고리즘 : 칼럼의 값으로 해시값을 계산해서 인덱싱하는 알고리즘. 매우 빠른 검색.

8.3 B-Tree 인덱스

B는 Binary의 약자가 아니라 Balanced를 의미한다.

8.3.1 구조 및 특성

  • 트리 구조의 최상위에 하나의 루트 노드(Root node)가 존재하고 그 하위에 자식 노드가 붙어있는 형태.
  • 가장 하위에 있는 노드는 리프 노드(Leaf node)라고 불린다.
  • 둘 다 아닌 중간에 있는 노드는 브랜치 노드(Branch node)라고 한다.
  • 리프 노드는 항상 실제 데이터 레코드를 찾아가기 위한 주솟값을 가지고 있다.

8.3.2 B-Tree 인덱스 키 추가 및 삭제

8.3.2.1 인덱스 키 추가

B-Tree에 저장될 떄는 저장될 키 값을 이용해 B-Tree상의 적절한 위치를 검색해야 한다. 위치가 결정되면 레코드의 키 값과 대상 레코드의 주소 정보를 리프 노드에 저장한다. 리프 노드가 꽉차면 리프 노드가 분리(split)되는데 상위 브랜치 노드까지 작업의 범위가 넓어진다.

8.3.2.2 인덱스 키 삭제

해당 키 값이 저장된 B-Tree의 리프 노드를 찾아서 그냥 삭제 마크만 하면 된다.

8.3.2.3 인덱스 키 변경

먼저 키 값을 삭제한 후, 다시 새로운 키 값을 추가하는 형태로 처리된다.

8.3.2.4 인덱스 키 검색

트리 탐색 : 루트 노드부터 시작해 브랜치 노드를 거쳐 최종 리프 노드까지 이동하면서 비교작업을 수행

8.3.3 B-Tree 인덱스 사용에 영향을 미치는 요소

칼럼의 크기, 레코드의 건수, 유니크한 인덱스 키 값의 개수 등에 의해 영향을 받는다.

8.3.3.1 인덱스 키 값의 크기
  • InnoDB 스토리지 엔진은 디스크에 데이터를 저장하는 가장 기본 단위를 페이지(Page) 또는 블록(Block)이라고 한다.
  • 디스크의 모든 읽기 및 쓰기 작업의 최소 단위이다.
  • B-Tree는 이진(Binary)가 아니기 때문에 자식 노드의 개수가 가변적이다.
  • 자식 노드의 개수는 페이지 크기와 키 값의 크기에 따라 결정된다.
  • 인덱스를 구성하는 키 값의 크기가 커지면 디스크로부터 읽어야 하는 횟수가 늘어나고 결국 느려진다.
  • 인덱스 키 값의 길이가 길어진다는 것은 전체적인 인덱스의 크기가 커진다는 것을 의미한다.
8.3.3.2 B-Tree 깊이
  • 직접 제어할 방법은 없다.
  • B-Tree의 깊이는 값을 검색할 때 몇 번이나 랜덤하게 디스크를 읽어야 하는지와 직결되는 문제다.
  • 인덱스 키 값의 크기가 커지면 커질수록 하나의 인덱스 페이지가 담을 수 있는 인덱스 키 값의 개수가 적어진다.
  • 따라서 같은 레코드 건수라 하더라도 B-Tree의 깊이가 깊어져서 디스크 읽기가 더 많이 필요하게 된다.
CATALOG
    MySQL