[데이터베이스] 데이터를 빠르게 찾게 해주는 Index

대량 데이터 내에서 검색하기

#

인스타그램의 검색 창에 내가 찾아보고 싶은 사람의 이름을 입력한다고 하자. 그러면 몇 초 만에 그 이름을 사용하는 사용자들이 뜬다. 인스타그램을 가입한 사람은 전세계에 수백만 명일텐데, 어떻게 이렇게 빨리 원하는 결과를 반환하는 것일까?

전체 검색을 하는 것은 대량 데이터에 적합하지 않다. 이것은 데이터의 양이 늘어날 수록 검색 시간도 똑같이 O(N) 으로 늘어나는, 선형 검색이다.

만약 데이터를 고정 길이로 저장한다면 ? 사용자 정보를 100byte 로 저장하는 경우, 사용자 ID * 100byte 째 로 이동한다면 사용자 정보를 저장하는 시작 위치가 된다. 그렇지만 사용자 이름이 너무 길어서 100byte 안에 안들어가면 문제가 생긴다. 그렇다고 고정 길이를 1000byte 로 늘리면 메모리 공간의 낭비가 된다.

실제 백엔드 서버를 구축하면, 프레임워크에 따른 차이보다 데이터베이스 설계와 쿼리에 대한 차이가 훨씬 크다. 그래서 서버의 성능을 올리고 싶다면, C++ 과 같은 고성능 언어를 도입하는 것이 먼저가 아니라, 데이터베이스 설계를 잘 해야 한다. 따라서 이 글에서는 데이터베이스 요청 응답 시간을 확 줄여주는 인덱스 개념에 대해 다뤄보고자 한다.

인덱스 구조의 도입

#

인덱스는 실제 파일의 위치를 담고 있는 특별한 자료구조이다. 인덱스의 존재 목적은 데이터를 빠르게 찾을 수 있게 하는 것이다.

인덱스 파일을 사용자 정보 파일과 별도로 관리할 수 있다. (사용자 ID : 바이트 위치) 형태로 인덱스 파일을 저장한다면, 사용자 ID = 123,492 에 대한 정보를 찾을 때 인덱스 파일에 접근해서 그 정보가 하드 디스크 상 어느 위치에 있는지 알 수 있다. 그러면 디스크 상에서 전체를 훑는 대신 사용자 위치로 바로 이동할 수 있다. 이 구조는 사용자 정보의 위치를 업데이트 하면, 인덱스 파일도 업데이트 해야 한다. 그리고 인덱스 파일은 고정 길이 파일 방식, 실제 사용자 정보는 가변 길이 파일 방식으로 저장할 수 있다.

Index vs. Primary Key

#

데이터베이스에는 Primary Key 가 있다. 그렇다면 PK 가 인덱스가 되는 것인가 ? 꼭 그렇지만은 않다. 둘은 애초에 존재 목적부터 다르다. 한번 자세히 구분해보겠다.

• Primary Key
  • 테이블 내 모든 튜플을 구분할 수 있게 해주는 속성 혹은 속성의 집합 (uniqueness, minimal) 을 모두 만족하는 속성을 PK 로 정한다.
  • PK 는 개념적인 값이다. 즉, PK 의 값이 따로 물리적으로 저장되는 것은 아닏.
  • 일반적으로 DBMS 에서는 PK 는 자동으로 index 가 적용된다.
  • Employee table 이 있을 때, 보통 Employee ID 가 unique , minimal 하므로 PK 로 많이 하지만, 다른 (unique, minimal) 속성을 만족하는 것이 있으면 그것을 PK 로 해도 된다.
• Index
  • 데이터를 빠르게 찾게 해주기 위해 데이터의 위치를 새로운 B+Tree 등 자료구조를 생성하여 별도로 (물리적으로) 저장하는 것이다.
  • Index 는 튜플들의 uniqueness 를 보장하지 않는다.
  • PK 는 Employee id 여도, index 에는 name 도 지정할 수 있다. 이것은 name 으로 검색하는 빈도가 훨씬 많은 경우이다.
  • CREATE [UNIQUE] INDEX index_name ON EMPLOYEE 명령어로 지정할 수 있다.

데이터베이스에서 데이터는 행에 저장되고, 이것들은 하나의 테이블을 구성한다. 각 행은 다른 행으로부터 구분되는 key 를 가지고 있다. 이 key 가 index 와 함께 저장된다.

해시 인덱스

#

키 값의 데이터 항목을 숫자, 문자열 등등 여러 포맷이라면 고정 길이로 접근하기 어려울 수 있다. 그래서 해시 함수에 넣어서 일정한 형태의 해시 값을 갖는 해시 인덱스를 도입한다.

해시 인덱스를 사용하지 못하는 경우도 있다. ex) 가격이 10,000원 이하의 선물을 갖고 싶다. -> 이 경우는 키 값이 여러개가 될 수 있기 때문에 해시 인덱스를 사용할 수 없다.

ex2) 제목이 ‘final’ 로 시작하는 게임을 사고 싶다. -> 이것은 범위 검색에 해당하는데 , 이 경우도 키 값이 여러개가 될 수 있기 때문에 해시 인덱스를 사용할 수 없다.

ex3) 일기 포스팅 시간이 최신 순으로 정렬하고 싶다. -> 이것은 sort 문제이다. 이런 순서에 따른 정렬도 해시 인덱스는 적합하지 않다.

이 것들을 위해 도입된 것이 B+ Tree 인덱스 구조이다.

B+ Tree 인덱스

#

정상(root block), 최하층 (leaf block), 그 사이에 branch block 으로 이루어진 트리구조이다. 루프 블록과 브랜치 블록은 검색의 키인 사용자 ID에 대해 해당 블록이 어디 있는지에 대한 정보를 가지고 있다. 그리고 리프 블록은 실제 저장 위치의 정보를 가지고 있다. 인덱스 검색 시 루트-> 브랜치 -> 리프 순서대로 인덱스를 탐색한다.

B+Tree 는 분기 개수가 여러 개인 다분기 트리이다. 분기 개수를 많이 하면 계층의 단수를 줄여서 액세스 횟수를 적게 할 수 있다. 이진 트리는 레코드 수 N당 탐색에 필요한 계산량이 O(log2N) 이지만, 다분기 트리는 계산량이 O(logmN) 이다.

B+ Tree 와 B- Tree

#

B+Tree 는 리프에서만 실제 저장 위치의 정보를 얻을 수 있었다. 하지만 B-Tree 는 브랜치에서도 값을 가질 수 있다. B+Tree 는 어떠한 검색이라 할지라도 루트에서 리프까지 와야지만 열의 값을 검색할 수 있다. 그렇지만 B+Tree 는 브랜치가 보다 단순해지므로, 인덱스 자체의 계층 구조를 작게 할 수 있다.

Reference

#

• https://www.freecodecamp.org/news/database-indexing-at-a-glance-bb50809d48bd/
• https://www.codecademy.com/article/sql-indexes
• https://stackoverflow.com/questions/5374908/what-is-the-difference-between-a-primary-key-and-a-index-key