DBMS에서 데이터 저장 방식 (Heap, ISAM, B+ Tree)

✅ DBMS에서 데이터 저장 방식

DBMS의 데이터 파일들은 주로 HDD나 SSD 같은 2차 기억장치에 페이지 단위로 저장되어 관리된다.

각 페이지에는 여러 개의 레코드가 저장되며, 각각의 레코드는 페이지에서 유일한 RID(레코드 아이디)를 가진다.

 

이 RID를 통해 해당 레코드에 랜덤 액세스 할 수 있다.

 

✅ 힙(Heap) 파일 구조

힙 파일 구조에서는 레코드가 파일의 빈 공간에 순서 없이 (즉, 정렬되지 않고) 저장된다.

 

그러나 대부분의 자료구조에서는 데이터 레코드만 봐서는 레코드의 RID를 직접 알 방법이 없기 때문에,
특정 데이터를 검색하려면 전체 페이지와 전체 레코드를 스캔해야만 한다.

 

파일 전체를 정렬된 상태로 유지하는 방법을 쓸 수도 있지만, 그런 방식은 파일이 클수록 비용이 많이 든다.

 

따라서 "인덱스"라는 보조 자료구조를 만들어 사용하여, 파일 전체를 정렬하지 않고도 검색 속도를 높일 수 있다.

 

📌 인덱스

인덱스란, 검색 속도를 높이기 위한 보조 자료구조이다.

인덱스는 특정 조건 (즉, 하나의 정렬 기준)에 따라 데이터의 RID를 정렬하여 저장함으로써,

인덱스를 통해 데이터에 접근할 경우 레코드에 빠르게 랜덤 액세스 할 수 있다.

 

인덱스 엔트리의 크기는 데이터의 크기보다 훨씬 작기 때문에,

인덱스 파일을 정렬 및 탐색하는 작업이 데이터 파일 전체를 직접 정렬 및 탐색하는 것보다 훨씬 빠르다.

 

그러나 인덱스의 크기가 커진다면 인덱스의 삽입, 삭제 비용도 커질 수 있다.

이것을 해결하기 위해 고안된 자료구조가 ISAM이다.

 

✅ ISAM (Indexed Sequential Access Method)

데이터에 대해 특정 기준으로 인덱스를 만들고, 이 인덱스를 계층 자료구조로 저장하여

이진탐색을 통해 레코드가 있는 위치(RID)를 빠르게 찾아내는 방식이다.

 

그러나 ISAM에서는 인덱스가 정적 구조로 설계되어 있기 때문에,

새로운 데이터가 추가될 때마다 인덱스를 재정렬하는 것이 아니라 새로운 오버플로우 페이지를 만들고 거기에 데이터를 연결한다.

오버플로우 페이지가 여러 개 연결된 것을 오버플로우 체인이라고 한다.

오버플로우 체인이 길어질수록 검색 속도가 저하된다는 단점이 있다.

 

이러한 단점을 개선한 구조가 B+ Tree 자료구조이다.

 

✅ B+ Tree

균형 트리 자료구조이다.

새로운 데이터가 추가될 때마다 인덱스가 트리에 삽입되면서 트리 균형이 자동으로 유지된다.

덕분에 ISAM에서처럼 긴 오버플로우 체인이 생길 일이 없다.

 

따라서 ISAM 구조보다 훨씬 효율적이며 좋은 성능을 낼 수 있다.