MongoDB Index#.2 B-Tree Index

by RastaLion · 2021년 3월 25일

MongoDB Index#.2 B-Tree Index

이전 포스팅

MongoDB Index #.1 - Architecture

MongoDB Index #.1 Index 란? DBMS에서 인덱스란 컬럼과 레코드가 저장된 위치를 key-value로 관리되어지는 검색 속도를 향상시키기 위한 자료구조 입니다. 프로그래밍 언어를 공부하다 보면 SortedList와 ArrayList라는 자료구조를 접하게 되는데, DBMS의 인덱스는 SortedList와 동일한 자료 구조이며 데이터 파일은...

B-Tree Index

이전 포스팅에서 MongoDB의 기본 인덱스는 B-Tree 인덱스로 되어 있다고 설명했습니다. B-Tree 인덱스는 MongoDB 뿐만 아니라 다양한 RDBMS들에서도 채택하고 있을 만큼 인덱싱 알고리즘 중에서 가장 일반적이고 오래된 알고리즘 입니다. 물론 DBMS의 종류에 따라 조금식 차이가 있지만, 전체적인 틀은 동일합니다.

MongoDB에서 단일 값을 가지는 필드나 배열 값을 가지는 필드는 인덱스안에 필드의 이름이 저장되지 않습니다. 반면 서브 도큐먼트를 값을 가지는 필드는 해당 서브 도큐먼트의 자식 필드의 이름이 모두 저장되므로 자식 필드의 이름이 길면 인덱스의 크기도 커지게 됩니다. 서브 도큐먼트의 자식 필드에 각각 인덱스를 생성하지 않고, 서브 도큐먼트 필드 자체에 인덱스를 생성하면, 서브 도큐먼트가 가지는 필드가 모두 존재하며, 순서가 모두 동일해야만 인덱스를 사용합니다.

인덱스 레인지 스캔

인덱스를 사용하는 방법 중에 인덱스 레인지 스캔은 특정 범위 내에서 인덱스 스캔을 시작할 위치를 선택하여, 스캔이 끝난곳에서 유저에게 결과 값을 반환하는 방식으로, 인덱스를 사용하는데 가장 대표적인 접근 방법입니다. 시작점을 찾기 위해서 루트 노드에서부터 비교를 시작하여, 브랜치 노드를 거쳐 마지막에 리프 노드의 시작 지점을 찾습니다. 리프 노드에서 시작 지점을 찾게 되면 리프 노드간의 링크를 이용하여 최종 지점까지 리프 노드만을 이용해 스캔을 합니다. 최종 지점에 도달하면 결과값을 유저에게 반환하며 처리 과정이 완료됩니다.

인덱스의 리프 노드에서 검색 조건과 일치하는 값들을 실제 데이터 파일에서 읽어오는 것은 랜덤 I/O가 발생하는 부분입니다. 10건의 데이터가 검색 조건에 일치한다면 10번의 랜덤 I/O가 발생하는 것이며, 이러한 이유로 인덱스를 통해 읽어야하는 데이터의 양이 전체의 15~20%를 넘으면 컬렉션 풀 스캔이 더 효율적입니다.

인덱스 프리픽스(Prefix) 스캔

문자열로 된 데이터를 검색하는 경우, 그 문자열과 동일한 데이터를 찾는 것이 아니라 일부만 일치하는 패턴을 가진 검색을 하게되는 경우가 많습니다. 이 경우 MongoDB 역시 정규식(Regular Expression)을 이용하여 문자열 검색을 수행할 수 있으며, MongoDB의 정규식은 PCRE(Perl Compatible Regular Expression)의 정규표현식을 사용합니다. 기존에 SQL의 정규식에 익숙하신 분들이라면 조금 사용법이 다르다고 느껴질 수 있습니다.

$regex 오퍼레이터를 이용하여 사용가능하며, 또는 $regex 오퍼레이터를 생략하거나 배열의 요소들을 매칭 시킬때 사용할 수 있습니다.

정규식 사용법

MongoDB의 기본적인 문법 구조는 아래 예시처럼 세가지 입니다.

db.collection.find({ name: { $regex: /pattern/, $options: '<options>' })
db.collection.find({ name: { $regex: "pattern", $options: '<options>' })
db.collection.find({ name: { $regex: /pattern/<options> })

pattern과 options를 조합하여 원하는 문자를 찾을 수 있습니다.

특정 단어가 포함된 도큐먼트를 찾을때는 / 또는 “”으로 단어를 묶어 줍니다.

> db.profile.find({username: { $regex: "Elsa" }})
{
  "_id" : ObjectId("60581cf7e6683f31fa784ee5"),
  "userId" : ObjectId("60581cf7e6683f31fa784ee2"),
  "username" : "Elsa",
  "title" : "엘사",
  "text" : "겨울왕국",
  "website" : "https://frozon.com"
}

> db.profile.find({username: { $regex: /Elsa/ }})
{
  "_id" : ObjectId("60581cf7e6683f31fa784ee5"),
  "userId" : ObjectId("60581cf7e6683f31fa784ee2"),
  "username" : "Elsa",
  "title" : "엘사",
  "text" : "겨울왕국",
  "website" : "https://frozon.com"
}

이처럼 “”를 사용하나 /를 사용하나 결과 값은 똑같고 패턴을 사용할 때도 동일한 결과를 보여줍니다.

정규식에 사용되는 패턴은 다음과 같습니다.

문자	설명
^ : 시작	이 메타문자 바로 다음에 오는 문자가 문자열의 맨 처음에 나타나야 한다. 패턴 예: ^h 일치하는 문자열: hello, h, hh 일치하지 않는 문자열: character, ssh
$ : 끝	이 메타문자 바로 앞에 있는 문자가 문자열의 끝에 나타나야 한다. 패턴 예: e$ 일치하는 문자열: sample, e, file 일치하지 않는 문자열: estra, shell
. : 임의의 문자	임의의 문자 한개와 일치한다. 패턴 예: hell. 일치하는 문자열: hello, hellx, hell5, hell! 일치하지 않는 문자열: hell, helo

정규식에 사용되는 옵션입니다.

옵션	설명
i	대/소문자를 구분하지 않음
m	multiline value에서 “^/$”가 포함된 패턴으로 조회할 때 각 줄의 시작과 끝을 조회 정규식에서 anchor(^) 를 사용할 때 값에 \n 이 있다면 무력화
s	정규식 안의 공백(whitespace), #(주석), 모두 무시
x	dot(.)을 사용할 때 \n를 포함하여 매치

다음은 대소문자를 무시하는 정규표현식 예제입니다.

대소문자 구분없이 h로 시작하며, h 다음에 오는 . 에 의해, h 다음에 어떤 문자든 1개가 있고, 그 다음 문자로 r 이 오는 유저명을 조회하는 쿼리입니다.

> db.profile.find({username: { $regex: /^h.r/i }})
/* 1 createdAt:2021. 3. 22. 오후 1:32:31*/
{
  "_id" : ObjectId("60581ddfe6683f31fa784eed"),
  "userId" : ObjectId("60581ddfe6683f31fa784eea"),
  "username" : "Harry Potter",
  "title" : "해리포터",
  "text" : "호그와트",
  "website" : "https://"
},

/* 2 createdAt:2021. 3. 22. 오후 1:36:25*/
{
  "_id" : ObjectId("60581ec9e6683f31fa784ef1"),
  "userId" : ObjectId("60581ec9e6683f31fa784eee"),
  "username" : "hermione",
  "title" : "헤르미온느",
  "text" : "호그와트",
  "website" : "https://her.net"
}

또 정규식을 사용하면서 *를 많이 보게 되는데, PCRE 정규분포식에서 *는 수량자로 * 앞에 있는 문자가 0회 이상 반복 되는 것을 의미합니다.

ha*t라고 표현을 한다면,

ht (hat 에서 a가 0회 반복 되었기에 ht가 됨), hat, haat, haaat 같은 단어는 표현식과 일치하는 것이 되며,

hut, hit 등 a가 있어거나 없어야 할 자리에 다른 문자가 들어와 있다면 일치하지 않는 것이 됩니다.

이렇게 간단하게 정규식을 이용하는 법을 알아보았고, 정규식을 이용한 문자열 검색은 인덱스 프리픽스 스캔을 활용합니다. 특히 인덱스 프리픽스 스캔을 할때 좌측부터 일치하는 문자열을 포함한 조건의 검색을 할때, 인덱스 레인지 스캔과 동일한 방식으로 작동하게 됩니다.

커버링 인덱스

앞에서 MongoDB는 데이터 파일뿐만 아니라 인덱스에도 값을 가지고 있다고 설명했습니다. 그래서 인덱스에 있는 데이터가 일치한다면 데이터 파일에 접근하지 않고, 인덱스에서만 값을 찾아 빠르게 사용자에게 반환하게 됩니다. 이렇게 인덱스만 가지고 데이터 값을 조회할 수 있는 최적화를 커버링 인덱스라고 합니다. 커버링 인덱스로 최적화 되어 있는경우 랜덤 I/O가 줄어들고, 성능이 향상됩니다.

MongoDB의 데이터 파일의 크기가 증가하면서 캐시에 필요한 데이터셋을 적재하지 못하는 경우 계속해서 디스크를 일어서 필요한 데이터를 가져와야 하는 상황이 발생합니다. 이때 현저한 성능 저하가 발생하는데, 이런 경우 커버링 인덱스를 통해 성능을 향상 시킬수 있습니다.

인덱스 풀 스캔

인덱스의 사이즈는 컬렉션의 사이즈 보다 작은 것이 일반적이며 컬렉션을 풀스캔 하는 것보다는 인덱스를 풀스캔 하는 것이 효율적입니다. 데이터를 조회할 때 특정 필드 값 전체를 가지고 처리해야 하는 상황에서 해당 필드에 인덱스가 생성되어 있다면, 컬렉션의 데이터에 엑세스 하지 않고, 상응하는 인덱스를 풀스캔 하여 처리할 수 있습니다. 레인지 스캔 보다는 느리지만, 컬렉션 풀스캔 보다는 빠르기 때문에 특정 필드를 모두 조회하는 경우가 잦다면 인덱스 풀스캔을 통해 전체 필드 값을 가져올 수 있습니다.

컴파운드 인덱스 (Compound Index)

컴파운드 익덱스는 하나의 필드가 아닌 2개 이상의 필드를 조합하여 인덱스를 생성하는 것입니다. 이때 필드의 순서가 중요한데, 앞쪽에 설정한 필드의 값을 먼저 읽고, 두번째 필드로 넘어가기 때문입니다. 실제로 첫번째 필드의 정렬은 리프 노드의 페이지 순서대로 정렬이 되어 저장이 되지만, 두번재 필드는 리프 노드의 각각의 페이지안에서 새로 정렬되기 때문에 두번째 필드의 정렬 순서가 빠르다 하여도, 첫번째 페이지의 정렬 순서가 늦다면 인덱스 뒤쪽에 위치할 수도 있습니다.

복합 필드 인덱스

컴파운드 인덱스를 생성하는 경우에 인덱스를 구성하는 필드들이 서로 다른 정렬 방식을 가질 수도 있습니다. 만약 첫번째 필드는 오름차순으로 정렬 하는 경우가 많고, 두번째 필드는 내림차순으로 정렬하는 경우가 많다면 정렬방식을 혼합해서 인덱스를 생성하는 것만으로 정렬효과를 가질수 있습니다.

MongoDB에서는 전문 검색 인덱스와 일반 단일 필드와 결합해서 인덱스를 생성할 수도 있고, 공간인덱스와 단일 필드값을 조합해서 인덱스를 만들수도 있습니다. 또 MongoDB의 컴파운드 인덱스는 결합된 필드 단위로 정렬 순서를 변경할 수 있는 장점이 있습니다.

다음 포스트

MongoDB Index#.3 Hashed Index

MongoDB Index#.3 Hash Index 이전 포스팅 MongoDB의 Hash Index 해시 인덱스는 B-Tree 만큼 범용적이지는 않지만 고유의 특성과 용도를 지닌 인덱스 중에 하나로, 주어진 키 값을 이용하여 목표 레코드의 주소를 직접적으로 계산하는 방식입니다. 따라서 단일...

참고 자료

도서 : 맛있는 몽고DB

도서: Real MongoDB

도서: 오픈소스 몽고DB

도서: MongoDB in Action

MongoDB Manual: https://docs.mongodb.com/manual/

Post Views: 986

소셜 미디어로 공유하기

MongoDB Index#.2 B-Tree Index