How tables and indexes are stored on disk
And how they are queried
데이터베이스를 이해하는 데 가장 중요한 기본 개념 중 하나는 테이블과 인덱스의 뒷단 그리고 이들이 디스크에 어떻게 저장되는지이다.
저장 관련 개념
테이블(Table)
- 열, 행
행 ID(Row_id)
- 내부 및 시스템에서 유지되는 값
- 특정 데이터베이스(예: MySQL - InnoDB)에서는 기본 키와 동일하지만, 다른 데이터베이스(예: Postgres)는 시스템 열인 row_id(tuple_id)를 가지고 있다.
페이지(Page)
- 저장 모델(행 저장 vs 열 저장)에 따라 행은 논리적인 페이지에 저장되고 읽힌다.
- 데이터베이스는 단일 행이 아니라 단일 IO에서 페이지 또는 그 이상을 읽습니다. 이러한 IO에서 많은 행을 얻을 수 있다.
- 각 페이지는 크기를 가지고 있다(예: Postgres에서는 8KB, MySQL에서는 16KB)
- 각 페이지는 3개의 행을 가지고 있다고 가정하면, 1001개의 행이 있으면 1000/3 = 333 페이지 정도가 된다.
IO
- IO 작업 (입출력)은 디스크로의 읽기 요청이다.
- 이를 최소화하려고 노력한다.
- IO는 디스크 파티션 및 기타 요인에 따라 1 페이지 이상을 가져올 수 있다.
- IO는 단일 행을 읽을 수 없습니다. 페이지에는 여러 행이 들어 있으며, 이를 무료로 얻을 수 있다.
- IO 횟수를 최소화하려고 노력해야 하며, 이는 비용이 많이 들기 때문이다.
- 운영 체제에서 일부 IO는 디스크가 아닌 운영 체제 캐시로 이동할 수 있다.
힙(Heap)
- 힙은 테이블이 모든 페이지를 연속으로 저장하는 데이터 구조이다.
- 여기에는 실제 데이터가 모두 포함된다.
- 힙을 탐색하는 것은 원하는 것을 찾기 위해 많은 데이터를 읽어야 하기 때문에 비용이 많이 든다.
- 이는 힙에서 읽어야 하는 부분을 정확히 알려주는 인덱스가 필요한 이유이다.
인덱스(Index)
- 인덱스는 힙과 별도로 있는 또 다른 데이터 구조로, 힙을 가리키는 "포인터"를 가지고 있다.
- 일부 데이터를 가지고 있으며 빠르게 검색하는 데 사용된다.
- 하나 이상의 열에 대한 인덱스를 생성할 수 있다.
- 인덱스의 값을 찾으면 힙으로 이동하여 힙의 모든 페이지를 스캔하는 데 드는 부담을 덜 수 있다.
- 인덱스도 페이지로 저장되며, 인덱스의 항목을 검색하기 위해 IO가 필요하다.
- 인덱스가 작을수록 메모리에 맞을 수 있으며 검색이 더 빨라진다.
- 인덱스에 대한 인기 있는 데이터 구조는 B-Tree이다.
참고 사항
- 때로는 힙 테이블이 단일 인덱스를 중심으로 구성될 수 있다. 이를 클러스터형 인덱스(clustered index) 또는 인덱스 기반 테이블(index organized table)이라고 한다.
- 기본 키는 (다르게 지정하지 않는 한) 일반적으로 클러스터형 인덱스이다.
- MySQL InnoDB는 항상 기본 키(클러스터형 인덱스)를 가지고 있으며, 다른 인덱스는 기본 키 "값"을 가리킨다.
- Postgres에는 보조 인덱스만 있으며, 모든 인덱스는 직접 힙에 있는 row_id를 가리킨다.
Primary Key vs Secondary Key
기본키(Primary Key)에 대한 설명을 하기 위해서는 먼저 테이블 space 또는 heap의 개념을 설명할 필요가 있다.
우리가 row store에 대해 얘기할 때, 테이블에 행이 있는 경우, 디스크에서 영역을 할당한다. 이를 보통 postgres에서는 heap으로 부른다. 다른 데이터베이스에서도 사용하는 용어이다. 이는 일반적으로 느린 액세스 공간이다. 최근에는 그렇게 많지 않지만, 모든 데이터, 비용이 많이 드는 데이터 세트가 있는 곳이다.
그리고 테이블은 기본적으로 행 단위로 구성된다. 테이블에 순서가 없고, 기본적으로 순서를 강제하지 않는다.
기본 키나 그와 유사한 것이 없다고 가정하자. 기본키를 추가할 때, 테이블에 대해 클러스터링이라는 작업을 수행한다. 클러스터링은 기본적으로 키를 중심으로 테이블을 조직하는 개념이다. 기본적으로 정렬을 유지하고, 삽입하는 행은 기본적으로 그 순서에 맞아야 한다. 이는 정렬에 관련된 추가 비용이 있음을 의미한다.
이로 인해 얻게 되는 좋은 점은 마치 테이블 자체에 인덱스가 있는 것 같다는 것이다. Oracle에서는 이를 IOT(인덱스 기반 테이블)라고 부른다. 클러스터형 인덱스나 기본키의 가장 큰 장점은 특히 범위 쿼리에서 속도가 빨라진다는 것이다.
보조키(Secondary Key)는 테이블을 정리되지 않은 채로 두고, 추가적으로 외부에 만든 구조물라고 볼 수 있다. 그게 바로 키이고, 인덱스이며, B-트리이다. 테이블은 정리되지 않은 채로 있다. 테이블 자체에 순서가 없지만 다른 구조물에서는 순서가 있는 것입니다. 인덱스를 위한 별도의 구조를 유지하고 있는 것이다.
클러스터링 인덱스 vs 비트리 인덱스
- 클러스터링 인덱스: 테이블의 레코드 자체가 인덱스 순서대로 물리적으로 저장됨
- B-Tree 인덱스: Balanced Tree 형태로 구성된 인덱스로, 키를 기준으로 데이터를 분할하여 저장
