데이터베이스 인덱스

 

인덱스를 사용해야하는 근본적인 이유

인덱스를 사용하는 이유는 무엇일까? 효율적으로 조회하기 위해서 일 것이다. 그럼 왜 풀텍스트 스캔을 하면 시간이 오래 걸리고, 인덱스를 사용하는 것이 더 효율적일까?

데이터베이스의 스토리지 엔진은 컴퓨터와 마찬가지로 하드디스크에 정보를 저장하고 읽어온다.

스토리지 엔진과 하드디스크

 

디스크는 아래 그림과 같이 구성되어 있다. 여기서 섹터는 하드 드라이브의 최소 기억 단위로 트랙의 일부이다. 만약 정보를 읽으라는 명령이 떨어지면 헤드와 암을 열심히 움직여 섹터를 탐색한다. 내용을 읽으려면 암과 헤드가 원하는 track으로 이동해야하고 (빙글빙글 돌고 있는 플래터의) 타이밍이 맞아 헤드와 섹터가 맞닿아야 한다. 이 과정 자체가 굉장히 느리기 때문에 효율적으로 디스크를 조회하려면 최소한의 섹터 범위 안에서 정보를 탐색하는 것이 가장 중요하다고 볼 수 있다.

섹터는 디스크의 종류에 따라 512바이트 섹터, 2048바이트 섹터, 4096바이트 섹터 등으로 용량을 고정되어 있다. 오래된 하드디스크의 경우 512바이트 섹터를 사용하는데 데이터베이스에서 해당 스펙을 사용한다고 가정하고 데이터베이스가 테이블의 내용과 인덱스를 저장하는 방식을 설명하도록 하겠다. 아래와 같은 테이블이 있다.

id(int)	name(varchar(8))	age(int)	intro(varchar(240))
1	park	26	안녕하세요~
2	kim	21	반갑습니다.

id는 4바이트/name은 8바이트/age는 4바이트/intro는 240바이트로 하나의 row당 256바이트를 사용해 저장한다고 해보자.

데이터가 약 1,000개 정도 저장되어있다고 가정한다면 1,000(개) * 256(byte) = 256,000 byte이다.

256,000 바이트를 섹터에 저장하려면 256,000(byte)/ 512(byte) = 500(섹터)이므로 데이터 1000개를 저장하기 위해 500개의 섹터가 필요하다. 해당 조건에서 풀스캔을 하면 최악의 경우 500개의 섹터를 모두 조회해야 정보를 찾을 수 있다.

 

여기서 인덱스를 사용하면 훨씬 적은 섹터로도 탐색이 가능하다.

primary key인 id는 자동으로 인덱스가 적용된다. 인덱스는 해당 값을 기준으로 정렬되고 해당 row의 주소값을 가리키는 pointer를 가지고 있다.

64비트 포인터(8 byte)라고 생각해보자. 그러면 id와 pointer를 합쳐서 12 byte가 된다. 총 1,000개의 row를 가지므로 12,000 byte의 값이 섹터에 저장될 것이다. 12,000(byte)/512(byte) = 23.4375(섹터) 이므로 총 24개의 섹터만으로 1,000개의 데이터를 저장할 수 있다. 테이블의 데이터가 저장된 500개의 섹터와 비교하면 20배의 차이다.

이게 인덱스의 힘이다. id를 통해 조회하면 탐색해야할 범위가 500개의 섹터에서 24개의 섹터로 줄어드는 마법을 경험할 수 있다. 그런데 여기서 B트리나 해시테이블과 같은 자료구조를 사용하면 24개의 섹터보다 더 적은 개수의 섹터만 조회해도 정보를 찾을 수 있다.

 

 

B트리

이진 트리(Binary Tree)의 진화된 버전으로 데이터가 삽입되거나 삭제되어도 지속적으로 균형(Balance)을 유지하는 트리이다. 덕분에 log(O)의 효율성으로 탐색을 진행할 수 있다.

B트리에 대한 영상을 하나 추천하고 싶다. 너무 잘 설명해주셔서 한 번만 봐도 B트리가 무엇인지 바로 알 수 있다.

링크: https://youtu.be/bqkcoSm_rCs

B+트리는 아래 블로그에서 정말 잘 정리해주셨다. 강력 추천!

[자료구조] 그림으로 알아보는 B+Tree