[PostgreSQL] B-tree index에 대해서 - 컴도리돌이

---

B-tree

PostgreSQL에서 기본적으로 사용되는 인덱스 구조는 B-tree로 되어 있습니다. B-tree는 데이터베이스에서 빠른 검색 및 정렬된 데이터 액세스를 위해 설계된 효율적인 인덱스 구조입니다.
 
B-tree의 인덱스 행은 페이지로 구성됩니다. 잎 페이지에서는 이러한 행에 데이터를 인덱싱할 키와 테이블 행(TID)에 대한 참조가 포함되며, 내부 페이지에서는 각 행이 인덱스의 자식 페이지를 참조하고 이 페이지의 최소 값을 포함합니다. 
 
B-tree의 몇 가지 중요한 특성이 다음과 같이 있습니다. 

• B-tree는 균현이 잡혀 있으며, 각 잎 페이지는 루트로부터 동일한 수의 내부 페이지로 분리됩니다. 따라서 모든 값에 대한 검색은 동일한 시간이 걸립니다.
• B-tree는 각 페이지(보통 8KB)는 많은(수 백개) TID를 포함합니다. 결과적으로 B-tree의 깊이는 매우 작으며, 매우 큰 테이블의 경우 실제로 최대 4-5입니다.
• 인덱스의 데이터는 비감소 순서로 정렬됩니다. 동일 수준의 페이지는 서로 양방향 리스트로 연결하며, 루트로 돌아가지 않고도 한 방향 또는 다른 방향으로 리스트를 거치면 정렬된 데이터 세트를 얻을 수 있습니다. 

---

B-tree 자료구조

https://junhkang.tistory.com/6?category=1136009

 
B-tree 구조에서 인덱스의 맨 처음 페이지는 메타 페이지입니다. 이 메타페이지는 인덱스의 루트를 참조합니다. 내부 노드는 루트 아래에 위치하고, 잎 페이지는 가장 아래에 존재합니다. 이때 아래쪽 화살표는 잎 노드에서 테이블 행(TID)으로의 참조를 나타냅니다.

---

CREATE TABLE books_test
(
    books_id    INTEGER NOT NULL PRIMARY KEY ,
    books_title VARCHAR ,
    books_price INTEGER ,
    books_link  VARCHAR ,
    books_pub   TIMESTAMP ,
    books_reg   TIMESTAMP
);

---

인덱스 동등 비교 탐색

https://junhkang.tistory.com/6?category=1136009

 
"인덱스 된 필드 = 표현식" 조건에 따른 트리 내 값의 검색을 살펴볼게요. 위에 설정한 테이블에서 books_id 값이 49인 것에 대해 탐색을 해보려고 해요. 쿼리를 작성하면 다음과 같습니다.
 

SELECT * FROM books_test bt WHERE bt.books_id = 49;

 
검색은 루트 노드에서 시작되며, 어떤 자식 노드로 내려갈지 결정해야 합니다. 루트 노드에 있는 키들(4, 32, 64)을 알고 있다면, 자식 노드에서 값의 범위를 파악할 수 있어요. 예를 들어, 32 ≤ 49 < 64 이므로 두 번째 자식 노드로 내려가야 합니다. 그다음, 같은 과정을 재귀적으로 반복하여 필요한 TID를 얻을 수 있는 잎 노드에 도달할 때까지 진행합니다. 
 
하지만 실제로 이렇게 간단한 과정이 이루어지지 않아요. 예를 들면, 인덱스에 중복되지 않는 키가 포함될 수 있고, 동일한 값이 많아서 하나의 페이지에 맞이 않을 수도 있어요. 위에 예제에서 내부 노드에서 값 49에 대한 참조를 통해 내려가야 하는 상황에서, 위에 그림과 같이 이전 잎 페이지에서 49 키 중 하나를 건너뛰게 됩니다. 따라서 내부 페이지에서 정확히 동일한 키를 찾았을 때, 왼쪽으로 한 칸을 내려가야 하고, 그런 다음 찾고 있는 키를 찾기 위해 하위 레벨의 인덱스 행을 왼쪽에서 오른쪽으로 확인해야 합니다. 
 

EXPLAIN SELECT * FROM books_test bt WHERE bt.books_id = 49;

Index Scan using books_test_pkey on books_test bt (cost=0.29..8.30 rows=1 width=160)
Index Cond: (books_id = 49)

 

---

NULLS

btree 인덱스는 "IS NULL" 및 "IS NOT NULL" 조건에 따른 검색을 지원합니다. NULL은 인덱스가 생성된 방식에 따라 잎 노드의 한쪽 끝에 위하게 되는데, 검색 명령에서 인덱스가 생성된 순서와 동일한 NULL의 순서를 ORDER BY절에서 지정하여 인덱스를 사용할 수 도 있습니다. 
 
쿼리가 데이터 정렬을 요구하고 인덱스가 필요한 순서를 보장한다면, 별도의 정렬을 절약하기 위해 인덱스 스캔을 선택할 수 있게 됩니다.
 

EXPLAIN SELECT * FROM books_test bt ORDER BY bt.books_link NULLs LAST

Index Scan using books_link_index on books_test bt (cost=0.41.. 4424.53 rows=29348 width=160)

 

---

인덱스 부등호 비교 탐색

https://junhkang.tistory.com/6?category=1136009

 
인덱스 된 필드가 주어진 표현식보다 작거나 같은 경우를 조건으로 검색할 때, 먼저 "인덱스 된 필드 = 표현식"의 동등 조건을 사용하여 인덱스에서 해당 값을 찾습니다.(만약 값이 존재할 경우)
 
그런 다음, 해당 값보다 큰 값들을 찾을 때까지 적절한 방향으로 잎페이지를 계속하여 이동합니다. 
 

SELECT * FROM books_test bt WHERE bt.books_id <= 32;

 
위에 예시에서는 인덱스에서 값 32 값을 찾은 후, 이보다 작은 값들을 찾을 때까지 왼쪽으로 이동하는 과정을 보여줍니다. 
 

EXPLAIN SELECT * FROM books_test bt WHERE bt.books_id <= 32;

Index Scan using books_test_pkey on books_test bt (cost=0.29..8.93 rows=32 width=160)
Index Cond: (books_id <= 32)

 

---

인덱스 범위 탐색

https://junhkang.tistory.com/6?category=1136009

 
범위 검색인 '표현식 1 ≤ 인덱스 된 필드 ≤ 표현식 2'로 검색할 때, 먼저 '인덱스 된 필드 = 표현식 1' 조건을 사용하여 해당 값이 있는지 찾은 후, 조건 '인덱스 된 필드 ≤ 표현식 2'가 충족될 때까지 잎 페이지를 계속해서 이동합니다. 또는 그 반대로, 두 번째 표현식부터 시작하여 첫 번째 표현식에 도달할 때까지 반대 방향으로 이동합니다. 
 

SELECT * FROM books_test bt WHERE bt.books_id >= 23 AND bt.books_id <= 64;

 
이 과정은 예를 들어, 조건 '23 ≤ n ≤ 64'인 경우를 설명하는데, 이는 먼저 '인덱스 된 필드 = 23' 조건으로 해당 값을 찾은 후, '인덱스 된 필드 ≤ 64' 조건을 충족시킬 때까지 오른쪽으로 계속 이동하는 과정을 보여줍니다.
 

EXPLAIN SELECT * FROM books_test bt WHERE bt.books_id >= 23 AND bt.books_id <= 64

Index Scan using books_test_pkey on books_test bt (cost=0.29..10.24 rows=42 width=160)
Index Cond: ((books_id >= 23) AND (books_id <= 64))

 

---

B-tree 인덱스 특징

• 동등 비교 및 범위 검색: 데이터가 동일한지 확인하거나 특정 범주에 있는 데이터를 조회할 때 사용됩니다. 예를 들어, 특정 날짜 범위 내의 주문을 조회하거나 특정 가격 범위 내의 제품을 검색하는 경우에 B-tree 인덱스를 사용할 수 있습니다. PostgreSQL 옵티마이저는 "<", "<=", "=", ">=", ">"와 같은 수식을 사용할 때 B-tree 인덱스를 고려합니다. 또한 IN 연산자나 BETWEEN 연산자를 사용하는 경우에도 B-tree 인덱스를 고려합니다.
• NULL 값 처리: IS NULL 및 IS NOT NULL 조건도 B-tree 인덱스를 사용하여 조회할 수 있습니다. 이는 NULL 값이 있는 열에 대한 조건을 포함하는 쿼리를 최적화하는 데 도움이 됩니다.

---

 

postgresql/개념/인덱스/B-tree 인덱스의 원리 및 특징.md at main · junhkang/postgresql

Indexes in PostgreSQL — 4 (Btree)

[PostgreSQL]  인덱스(INDEX)개념 및 생성, 삭제, 분석, 설계 방법