DataBase Index 개념 정리하기

Index에 대해서 공부해 보자😀

오늘은 index란 것에 대해서 정리해 볼까 합니다.

 

아무래도 DB를 구축하고 운용하는 것에 그치지 않고, 성능을 개선하기 위해 index라는 자료 구조가 꼭 필수적이기 때문에 개념을 정리하게 되었습니다.

---

Index 란?

일단 인덱스는 서두에서도 언급했다시피 자료 구조에 해당합니다. 

 

이 자료 구조는 데이터 테이블에 저장된 데이터들을 조회하는 속도를 빠르게 하기 위해 사용합니다. 

 

Index와 연관된 기본 용어부터 정리해봅시다.

• search-key: search-key는 하나 이상의 속성들(attributes) 집합입니다.
• index file: search-key와 pointer를 쌍으로 하는 records들로 구성된 형태입니다.

index file 구조

여기서 search-key를 구성하는 속성들은 테이블의 칼럼에 해당합니다.

 

그러니까 search-key는 index 자료구조를 이용해서 빠르게 조회할 속성들의 집합이라고 볼 수 있습니다.

 

앞서 index는 자료구조라고 정리한 바가 있습니다. 그렇기 때문에 index도 결국에는 특정 자료구조 형태로 구현되어 있어야 하는데, 이에 대해 정리하기에 앞서 먼저 index의 종류부터 정리해 보도록 하겠습니다.

---

Index의 종류

다음 두 가지의 Index가 존재합니다.

• Primary Index
  • clustering index라고도 불립니다.
  • 실제 데이터가 정렬된 순서와 같은 순서로 정렬된 search-key에 따른 records를 갖는 index입니다.
• Secondary Index
  • non-clustering index라고도 불립니다.
  • primary index와는 다르게 실제 데이터가 정렬된 순서와 다른 순서로 정렬된 search-key들에 따라 records를 갖는 index입니다.

말로 바로 받아들여 지기에는 조금 복잡하기 때문에, 그림으로도 한 번 그려봤습니다.

 

우선 primary index (clustering index)입니다.

primary index 예시를 간단하게 그려봤습니다.

왼쪽의 초록색 테이블이 primary index라고 할 수 있습니다.

 

그림을 보면 알 수 있듯이 오른쪽 테이블이 id라는 칼럼(속성)을 기준으로 정렬되어 있고, 인덱스 또한 id의 순서에 따라 정렬되어 있음을 확인할 수 있습니다.

 

이렇게 인덱스의 search-key가 테이블의 정렬 순서에 따라 같은 순서로 정렬된 index를 primary index라고 부릅니다.

 

다음은 secondary index (non-clustering index)입니다.

secondary index 예시도 그려봤습니다.

이렇게 secondary index는 데이터 테이블이 데이터를 저장하고 있는 순서와 다른 순서로 search-key에 따른 records를 저장하고 있습니다.

 

사실 위의 예시들은 index를 만들다 말아서, 원래는 dense index, sparse index 여부에 따라

• dense index: 모든 데이터를 가리키는 records가 있다.
• sparse index: 일부의 데이터를 가리키는 records만 있다.

이렇게 나뉘게 됩니다.

 

그렇기 때문에, dense index 형태의 index를 그리려고 하였으나 나머지 데이터를 생략한 구조로 이해해 주시면 좋을 것 같습니다.

 

다시 돌아가서, 그렇다면 왜 primary index와 secondary index를 사용하는 것일까요?🙄

 

그 이유는 다음과 같습니다!

• Primary Index
  • 주로 primary key를 search-key로 갖는 index일 때, primary index 구조입니다.
  • primary index는 데이터 테이블이 데이터를 정렬하는 것과 같은 순서로 record를 보유하고 있기 때문에, 탐색 속도가 빠릅니다.
• Secondary Index
  • 주 식별자나 primary index가 있는 search-key를 기준으로 탐색하는 상황 말고도, 데이터 테이블에서 특정 조건에 맞는 데이터를 조회하고 싶은 상황이 존재할 수 있습니다.
  • 예를 들어 특정 부서에서 근무하는 사원 정보만을 조회하고 싶은 경우, 보통은 사원 테이블은 사원 id를 주 식별자로 삼기 때문에, 부서에 따른 검색을 index를 이용해 최적화하고 싶다면 secondary index를 사용할 수 있을 것입니다.

 

앞서 살짝 나왔던 sparse, dense index의 차이점도 정리해 보겠습니다.

• Sparse Index
  • 의미를 보면 알 수 있듯이, 뜨문뜨문하게 records를 갖고 있는 index를 의미합니다. 
  • 즉, 모든 데이터에 대해 record를 갖지 않습니다.
• Dense Index
  • Sparse index와 반대로 모든 데이터에 해당하는 records를 갖습니다.
  • secondary index의 경우에는 무조건 dense index입니다.
    • 이는 secondary index가 데이터 테이블이 데이터를 정렬한 순서와 다른 index 이므로 데이터 테이블 내의 모든 데이터를 정상적으로 찾기 위해서는 각 데이터에 맞는 record가 필요하기 때문이죠

---

Index를 구현하는 자료구조들

Index의 구현을 위해 사용하는 자료구조는 대표적으로 2가지입니다.

• Hash Table
• B+ Tree

이 두 가지의 자료 구조는 하나씩 다뤄도 내용이 너무 방대해서 간단하게만 정리하겠습니다.

 

Hash Table

Hash table은 hash function (해시 함수)와 search-key의 값을 이용해 계산한 결과로 우리가 원하는 record의 bucket을 찾는 방식으로 데이터를 조회합니다.

 

그렇기 때문에, 해시 함수에 값을 넣고 계산만 하면 데이터 검색을 할 수 있기 때문에, 검색 속도가 아주 빠르죠.

 

이 bucket이라고 하는 단위는 하나 이상의 records를 포함하는 저장소의 단위를 의미합니다. 보통 dick block 하나의 사이즈가 bucket 하나의 사이즈와 동일하다고 합니다.

 

예를 들어 search-key가 사람의 이름이고, 이름이 "철수"라면, 해시 함수 h를 이용한 연산이 다음과 같이 이루어집니다.

h("철수") = 3

 이렇게 해시 함수 결과 값이 3이면, 이름 칼럼의 값이 "철수"인 데이터는 3번 bucket에 있다고 판단하는 것입니다.

bucket들

이렇게 bucket에 들어가면, search-key value와 함께, pointer 정보를 갖고 있는 records가 있고, 알맞은 records의 pointer에 접근해 실제 데이터 테이블의 데이터에 접근할 수 있게 됩니다.

 

이런 방식으로 데이터를 조회하기 때문에, 해시 함수로 무엇을 사용하는지도 굉장히 중요합니다.

 

왜냐하면 해시 함수 결과로 각 bucket에 들어가는 records가 uniform and random 해야 하기 때문입니다.

 

이것은 해시 함수 결과로 하나의 bucket에만 데이터가 몽땅 쏠리는 상황을 생각해 보면, 문제가 어떤지 짐작할 수 있습니다.

 

B+ Tree

B+ Tree는 가장 널리 index 구현에 사용되는 자료구조라고 합니다.

 

B+ Tree는

• balanced tree 이기 때문에, 모든 leaf node가 같은 length를 가지려 합니다.
• multi-level tree 이기 때문에, 부모 노드가 여럿의 자식 노드를 갖습니다.
• leaf node만 데이터에 대한 pointer를 직접 저장하고(record처럼), 나머지 노드(인덱스 노드)들은 key만 갖습니다.
• leaf node의 마지막 pointer는 다음 leaf node를 가리켜서, 효율적인 연속 처리가 가능합니다.

B+ Tree를 제대로 정리하려면, 너무 길어서 글로만 정말 간단하게 정리를 해봤습니다.

 

궁금하신 분들은 B+ Tree에 대한 정리글을 찾아보시면 좋을 것 같고, 저도 기회가 된다면 나중에 한 번 정리해보려고 합니다..

---

정리하기

사실 Index를 사용하는 것이 여기까지 오면 무조건 좋아 보이지만, 그렇지 않습니다.

 

Index 자료구조를 사용하면, 조회 속도를 최적화할 수 있다는 장점이 있지만, 데이터 테이블과 별개로 추가적인 자료구조를 하나 관리하는 것에 대한 비용도 고려해야 하고, 무엇보다도 Index를 유지함에 따라서 insert, update, delete 연산의 비용이 증가합니다.

 

이는 앞서 살펴본 hash table이나 B+ Tree에서의 insert, update, delete 과정의 영향이 있습니다.

 

하지만, 대부분의 서비스에서 조회 서비스의 점유율이 높다고 판단되어 Index를 사용한 성능 최적화가 많이 이루어진다고 어떤 강의에서 들었던 것 같습니다..

 

여튼 오늘은 여기까지 정리하고, 다음에는 실제로 DBMS와 더미 데이터를 이용해서 Index를 사용하면 얼마나 성능이 개선되는지 테스트해보려고 합니다.