INDEX에 대하여 .. 조금 더 깊은 이야기 (Postgres 와 datapage)

INDEX란 .. 간단하게 이야기하면 하나의 테이블의 레코드와 그 레코드가 담긴 데이터 페이지의 매핑정보를 담아놓은 구조라고 볼 수 있다. 또한 랜덤 액세스는 인덱스가 제공하는 중요한 이점 중 하나이다.

 

PostgreSQL에서 인덱스는 테이블의 특정 컬럼 값과 해당 값이 저장된 위치 정보를 연결해, 쿼리를 효율적으로 실행할 수 있게 돕는다. 이 정보를 통해 데이터베이스는 테이블 전체를 탐색하지 않고도 필요한 데이터를 빠르게 찾아낼 수 있다.

 

인덱스의 역할

인덱스는 특정 컬럼의 값과 그 값이 저장된 데이터 페이지 번호와 페이지 내 위치(오프셋)를 연결한다. PostgreSQL에서는 이 정보를 TID(Tuple Identifier)라고 부르며, TID는 해당 데이터가 저장된 페이지 번호와 행의 위치(오프셋) 정보를 포함한다. 이를 통해 PostgreSQL은 테이블에서 데이터를 읽을 때 시퀀셜 스캔 대신 인덱스 스캔을 사용할 수 있으며, 필요한 데이터가 있는 정확한 위치를 빠르게 찾아낼 수 있다.

 

사실 페이지 자체도 논리적인 개념으로 디스크든 메모리든 어딘가 물리적 위치에 자리잡게된다. 이때 물리적인 위치는 랜덤엑세스하게되고 내가 찾아야하는 데이터가 담긴 페이지의 '논리적 페이지 번호(인덱스로 관리하기 위해 pg가 부여한)' 를 찾으면 해당 페이지를 Shared Buffers에 로딩하고 그 페이지 안에서 offset으로 레코드를 탐색하여 정보를 꺼낸다. 

 

인덱스가 없다면, 데이터베이스는 테이블의 모든 행을 처음부터 끝까지 순차적으로 탐색해야 한다. 그러나 인덱스를 사용하면, 해당 컬럼의 값을 기준으로 데이터가 저장된 위치를 미리 알고 있어, 디스크에서 필요한 데이터 페이지로 바로 이동할 수 있다. 이로 인해 쿼리 실행 속도가 대폭 향상된다. (바로 이동이라는 표현이 과격할 순 있으나 어쨌든 풀스캔에 비해서이니 양해부탁드린다.)

 

인덱스는 메모리와 디스크 모두에 적용된다. 데이터베이스는 먼저 메모리인 Shared Buffers에 해당 페이지가 있는지 확인(이 과정에서도 랜덤엑세스)하고, 없으면 디스크에서 해당 페이지를 로드해 메모리로 가져온다. 페이지를 메모리로 로드한 후에는 오프셋을 통해 해당 페이지 내에서 데이터를 찾아낸다. 따라서 인덱스는 디스크에서 데이터를 로드할 때도, 메모리에서 데이터를 검색할 때도 성능을 최적화하는 중요한 도구이다. 따라서 인덱스는 필요한 데이터 페이지의 위치를 미리 알고 있으므로, 디스크 I/O(입출력) 비용을 크게 줄여준다.

 

B-트리 인덱스

PostgreSQL에서 가장 흔히 사용되는 인덱스 유형은 B-트리 인덱스이다. B-트리 인덱스는 컬럼의 값을 기준으로 데이터를 트리 구조로 정렬하고 저장하며, 검색할 때는 트리를 탐색하여 값을 빠르게 찾는다. 트리의 리프 노드에는 해당 값이 저장된 데이터 페이지 번호와 오프셋이 매핑되어 있어, 이를 통해 데이터베이스는 디스크에서 특정 페이지에 빠르게 접근할 수 있다.

 

출처 : https://medium.com/@egorponomarev/b-tree-index-in-postgresql-b4e3ac8ed92f

 

 

이 그림은 B-트리 구조에서 특정 값을 탐색하는 과정을 설명하는 예시이다. 여기에서 -6 값을 찾는 과정을 알아보자

1. 루트 노드에서 탐색 시작:

• 탐색은 항상 루트 노드에서 시작됩니다. 루트 노드에는 -15, 10, 25가 있다.
• -6은 -15보다 크고, 10보다 작기 때문에, 루트 노드에서 -15와 10 사이의 자식 노드로 이동.

2. 첫 번째 중간 노드로 이동:

• 이제 -15와 1 사이의 자식 노드로 이동하게 됩니다. 이 중간 노드에는 -15, 1, 4가 있다.
• -6은 -15보다 크고, 1보다 작기 때문에, -15와 1 사이의 자식 노드로 다시 이동

3. 리프 노드로 이동:

• 리프 노드에는 실제 데이터가 저장되어 있으며, 여기에서 -6 값을 찾는다.
• 그림에서 보면 -6은 리프 노드에 있는 데이터 중 하나이며, 해당 값을 찾게 된다.

전체 경로 요약:

1. 루트 노드에서 -15와 10 사이의 자식 노드로 이동.
2. 중간 노드에서 -15와 1 사이의 자식 노드로 이동.
3. 리프 노드에서 -6 값을 찾아서 데이터에 접근.

이 과정을 통해 B-트리는 데이터를 효율적으로 탐색하며, 트리의 각 단계에서 범위에 따라 적절한 자식 노드로 이동하게 된다.