본문

DB 인덱싱의 기본 원리와 이해

도입

이번 포스팅에서는 인덱스를 이해하고 적절한 설계 방법에 대해 정리할 예정이다.


Database의 처리 단위

DBMS에 따라 다르다. 대표적으로

Oracle

block단위 (2 ~ 64kb, config로 설정 가능)

Oracle manages the storage space in the datafiles of a database in units called data blocks. A data block is the smallest unit of data used by a database. In contrast, at the physical, operating system level, all data is stored in bytes. Each operating system has a block size. Oracle requests data in multiples of Oracle data blocks, not operating system blocks.

The standard block size is specified by the DB_BLOCK_SIZE initialization parameter. In addition, you can specify of up to five nonstandard block sizes.

https://docs.oracle.com/cd/B19306_01/server.102/b14220/logical.htm#i4894

MySQL

page단위 (16kb로 고정)

InnoDB stores all records inside a fixed-size unit which is commonly called a "page" (though InnoDB sometimes calls it a "block" instead). Currently all pages are the same size, 16KB.

https://dev.mysql.com/doc/internals/en/innodb-page-structure.html

 

각 테이블의 row 사이즈에 따라 page할당 개수가 달라진다. page가 많아질 수록 성능 저하가 발생할 수 있다. 
(물리적 위치가 다를 수 있으므로 disk에서 데이터를 가져올 때 page 단위로 가져온다.)

page가 클수록 효율적이다?

  • 사용하지 않는 데이터를 cache에 추가하므로 buffer Pool의 공간이 줄어 효율성이 떨어진다.
  • 비어있는 row로 구성된 page가 생겨 빈공간으로 효율성이 떨어진다.

적절한 Size가 중요!


Index 구조와 원리

  1. Index 개념
    index의 사전적 의미는 목차 (e.g. 책에서 목차로 데이터를 한번에 찾을 수 있다.)

  2. Index 필요 이유
    목차가 없다면 data를 찾기 위해 처음부터 끝(table full scan)까지 확인해야한다.
    (중간에 찾더라도 마지막에 또 있을 수 있으므로 마지막까지 확인해야 한다.)

  3. DB에서 Index
    B-TREE Index, R-TREE Index, BITMAP Index 다양한 방식 존재
    그러나 B-TREE Index가 대부분 사용되고 대부분 처리 가능

  4. Index 탐색 방법
    key-주소값(실제 데이터를 갖고 있지 않다)으로 데이터 존재
    수직 탐색: Root block 방문 -> 조건에 따라 브랜치 block 방문
    수평 탐색: 몇개의 leaf가 있는지 확인

  5. Index 비효율 케이스

    1. 데이터가 많은 경우: 분기를 하기 위해 많은 branch 필요, 그러므로 B-Tree의 dept가 깊어진다.
    2. 너무 긴 컬럼을 index로 사용하는 경우: 하나의 page가 아닌 많은 page로 설정되면 buffer pool에 hit율이 낮아진다.

http://www.dbguide.net/publishing/img/knowledge/SQL_244.jpg


결합 Index의 원리

결합 Index 설정에 따라 시스템의 성능이 판단된다.

  1. 결합 Index 개념
    2개 이상의 컬럼을 Index로 구성하는 것, 여기서 맨 앞 index되는 컬럼을 선행 컬럼이라 한다.

  2. 장점
    단일 index로 중복값이 많다면 효과적이다.
    (e.g. 단일 index -> 결합 index
    SQL: ... WHERE name ="heepie" AND location = "seoul" (index: location)
    AS-IS: seoul을 찾았지만 이후 seoul 군집에서 모든 사람을 확인해야한다.
    TO-BE: index에 name추가, seoul에서 heepie를 찾은 후 수평 탐색만 진행)

  3. 단점
    선행 컬럼 조건이 없다면, 비효율적(table full scan)
    (e.g. index: location, name 이라도
    SQL: ... WHERE age = "10" AND name ="heepie" AND location = "seoul"
    age를 위해 table full scan이 발생하므로 비효율적이다.)


개선안

  1. Index 순서 변경
    Index 순서 변경으로 선행 컬럼의 조건 범위 개선
    (e.g. seoul에 거주하는 사람 1000명, heepie는 1명, SELECT name, location, age
    AS-IS: index가 [location + name]이면 location에서 1000번의 table random access 발생
    TO-BE: index가 [name + location]이면 name에서 1번의 table random access 발생)

  2. Table Random Access 최소화
    Coverage Index(Index only, disk i/o X) 설정을 위해, Index 추가

'컴퓨터 > 이론: 개발' 카테고리의 다른 글

DB 인덱싱과 최적화  (0) 2020.07.27
DB 인덱싱의 기본 원리와 이해  (0) 2020.07.26
DB 아키텍처와 성능 관리  (0) 2020.07.21
DB Modeling  (0) 2020.07.20
HashMap 동작원리 및 충돌해결  (0) 2020.07.15
프로세스 VS 쓰레드  (0) 2020.07.14

공유

댓글 0