[PostgreSQL] PostgreSQL의 B-tree, Hash Index에 대해서 알아보자.

RDBMS에서 핵심 기능 중 하나인 인덱스의 종류에 대해 알아보자.

 

인덱스를 특정 데이터를 빠르게 가져오는 기술이다.

 

일반적인 예로 백종원의 레시피 책을 본다고 하자.

근데 우리는 짜장면 레시피를 확인하고 싶다면 일일이 처음부터 짜장면이 나올 때 까지 찾을 수 있겠지만,

책의 색인을 통해서 'ㅈ'(지읒)을 찾고 지읒에 있는 리스트들을 쭉 내려가면서 짜장면이라는 단어를 찾고

해당 페이지로 넘어가는 방법도 있을 것이다.

 

 

바로 DB에서 후자의 기술을 인덱스라고 할 수 있다.

 

공식 문서에서 인덱스를 찾아보면

---

Indexes are a common way to enhance database performance.

An index allows the database server to find and retrieve specific rows much faster than it could do without an index.

But indexes also add overhead to the database system as a whole,
so they should be used sensibly.

---

인덱스는 퍼포먼스를 강화시키는 일반적인 방법

특정 row를 더 빠르게 반환해준다.

그러나 많이 쓰면 overhead가 발생한다.

그래서 우리는 현명하게 사용해야한다.

 

기본적으로 인덱스는 CREATE INDEX 키워드를 통해 생성할 수 있다.

 

 

 

(1) B-Tree

 

B-Tree 인덱스는 기본적인 인덱스로 가장 많이 쓰이는 인덱스이며

생성할 때 명시를 하지 않으면 자동적으로 B-Tree로 생성된다. (명시를 해도 된다. 굳이?) 

CREATE INDEX test1_id_index ON test1 (id);

 

 

B-Tree 알고리즘을 사용하는 인덱스이다.

 

Root : 최상위 노드

Branch : Root와 Leaf 사이에 있는 노드

Leaf : 마지막 노드

 

 

 

B-Tree는 균형 트리로 어느 한쪽으로 치우쳐져 있지 않고

각 레벨과 그 레벨의 노드의 수를 균일하게 유지해서 빠르게 찾을 수 있다.

 

 

만약 아래 그림과 같은 B-Tree 인덱스가 있고

8을 찾는다고 하면 아래 빨간 화살표 방향으로 가고

Leaf 노드인 6인데 8보다 작으므로

6부터 시작해서 8이 나올 때 까지 찾을 것이다.

 

따라서 4 -> 8 -> 6 -> 6 -> 8 로 찾을 것 이다.

 

 

 

B-Tree 알고리즘을 좀 더 이해하고 싶다면

아래 사이트에서 값이 들어가고 찾는 과정을 눈으로 보면 이해가 더 쉬울것 같다.

 

B-Tree Visualization

 

B-Tree 인덱스의 자세한 활용은 추후 게시물에서 다루도록 하겠다.

 

 

(2) Hash

 

Hash indexes can only handle simple equality comparisons.

Whenever an indexed column is involved in a comparison using the = operator.

 

Hash 인덱스는 Hash 자료구조로 인덱스를 다룬다.

USING HASH 키워드로 B-Tree와 다르게 반드시 명시를 해줘야 한다.

CREATE INDEX name ON table USING HASH (column);

 

 

B-tree로 '=' 연산으로 찾아보았다.

CREATE INDEX num_index ON test_index(num);
EXPLAIN ANALYZE SELECT * FROM test_index WHERE num = 5000000;

Result

 

 

 

'=' 연산자로 검색 시 Index Scan을 확인할 수 있다.

CREATE INDEX num_index_hash ON test_index USING HASH (num);
EXPLAIN ANALYZE SELECT * FROM test_index WHERE num = 5000000;

Result

 

 

공식 문서에는 '=' 연산 시 B-tree보다 빠르다고 했는데

실제 천만 row로 테스트를 진행해보았을 때

실제 B-tree와 찾는 속도는 크게 체감하지 못했다.

우리가 실제로는 체감을 못했지만 내부적인 프로세스로는 Hash가 더 빠르다고 한다.

 

 

B-tree로 범위 검색

CREATE INDEX num_index ON test_index (num);
EXPLAIN ANALYZE SELECT * FROM test_index WHERE num > 300000;

Result

 

정상적으로 인덱스 스캔을 확인할 수 있다.

 

 

 

 

Hash로 범위 검색

CREATE INDEX num_index_hash ON test_index USING HASH (num);
EXPLAIN ANALYZE SELECT * FROM test_index WHERE num > 300000;

Result

 

인덱스가 걸리지 않는다.

 

 

 

** 해쉬는 왜 '=' 연산만 가능할까?

key 값이 조금만 차이가 있어도 전혀 다른 해싱값을 갖기 때문에

기본적으로 값이 정렬되어 있다고 볼 수 없다.

해싱된 값에 따라 저장될 버킷 위치를 정하기 때문이다.

 

 

 

초반에 적긴했지만 우리는 현명하게 인덱스를 사용해야 한다.

일반적인 상황에서는 B-tree를 사용하는게 좋고

SELECT 에 조건을 '='만 사용한다면 Hash 인덱스를 사용하는게 좋다. 

 

 

 

REFERENCES

PostgreSQL : Documentation: 13: PostgreSQL 13.7 Documentation