B-Tree 알고리즘 (DB 인덱스의 내부 알고리즘)

Why

오늘은 B-Tree 알고리즘을 쉽게 풀어 보겠습니다.

이 알고리즘은 수많은 데이터에서 내가 원하는 데이터를 찾는 알고리즘 인데요.

DB에서 많이 사용 됩니다.

정확하게는, DB 의 Index가 데이터를 빨리 찾는 이유죠.

데이터에서 무엇인가 찾는다는 것

이 글을 읽는 분들은 모두 DB 사용 경험이 있으실겁니다.

여기, 셀수도 없이 많은 사람 이름 데이터가 있습니다.

우리 한번, 여기서 “김”씨를 다 찾아봅시다.

사람이라면, 이렇게 찾겠죠.

일단 모든 데이터를 종이에 프린트 하고요.

자 하나와 펜을 들고…

한줄 한줄 가리키며 김 씨면 동그라미를 치고..몇페이지의 몇번째 줄인지 어딘가 적겠죠?

1페이지에서 찾는데 5분이 걸린다 가정하면, 1000페이지면 3일 넘게 걸립니다.

어휴 끔찍하네요.

그런데, 컴퓨터가 이 작업을 그대로 한다고 해봅시다.

사람 처럼 똑같이 모든 데이터를 일일히 돌려서 확인하는 방법이 직관적이겠죠?

그런데, 사람보다는 엄청 빠를 겁니다.

1000페이지 수준이라면 0.1초도 안 걸릴거에요.

이 방식은 이렇게 모든 데이터를 순환하여 찾는다. 결국 모든 데이터를 한번씩 보게 되기 때문에 전부 다 읽는다는 의미로

Full Scan 방식 이라고 하며 순차 검색 방식 이라고도 합니다.

그런데, 1억 페이지라면?

한번 계산해 보죠.

사람: 1페이지 5분, 1억 페이지 5억분, 음... 951년 걸리네요.

컴퓨터: 1페이지 0.1초, 1억 페이지 1천만초, 사람보다 3000배(5분=300초) 빠르니까... 약 3개월 걸립니다.

1페이지에 0.1초 밖에 안걸린다고 해도, 1억 페이지는 3개월이 걸립니다.

이래가지고는 Full-Scan은 실전에서 도저히 쓸 수가 없겠죠?

실제로는 더 빠르게 동작하고, 내부적으로 여러 방법을 쓰기 때문에 1억건 풀스캔에 1시간 정도 걸리게 됩니다.

하지만 그래도, 1시간은… 너무 느립니다.

B-Tree 는 무엇이길래?

바로 위와 같이 데이터가 엄청 많을 때, Full Scan 이 느린 문제를 해결하기 위해 사용하는 알고리즘 인데요.

B-Tree는 Binary Tree의 약자로, 이진 트리 기반의 자료구조 알고리즘입니다.

갑자기 바이너리 트리, 이진 트리 하니까 어렵게 느껴지죠?

오늘 이걸 한번 쉽게 배워봅시다.

주니어 엔지니어도 이해할 수 있게 아주 쉽게 풀어볼께요.

쉽게 설명하기 위한 약간의 무리수는 있지만, 이해하는데 큰 문제는 없을 거예요.

일단, B-Tree 검색이 빠른 이유

생각보다 간단 합니다.

• 애초에 찾기 쉽게 데이터를 폴더 마냥 분류해 두는 것입니다.
• 이때, B-Tree 답게, 뿌리에서 가지 치기 하듯, 분류하여 아래 모양 처럼 저장 합니다.

뿌리
├── 김
│ ├── 김가
│ │ ├── 김가네
│ │ │ ├── 김가네가 (5페이지 16줄, X페이지 X번줄, ...)
│ │ │ └── 김가네고 (12페이지 186줄, X페이지 X번줄, ...)
│ │ └── 김나네 (98페이지 44번줄, X페이지 X번줄, ...)
│ └── 김노
│   └── 김노네 (X페이지 X번줄, X페이지 X번줄, ...)
└── 이 
  ├── 이가  
  │ └── 이가네 (X페이지 X번줄, X페이지 X번줄, ...) 
  └── 이갈 
	├── 이갈이 (...) 
    └── 이갈비 (...)

• 대충 이해하기 쉽게 위와 같이 분류를 데이터가 저장 될 때마다 하는거죠.
  (실제는 이보다 복잡 합니다.)
• 이렇게 저장을 잘 해두었다면? 이제 찾는건 쉽습니다.

B-Tree 에서 찾기

• 위 예시처럼 김씨를 B-Tree 로 찾아봅시다.
• 우선 뿌리에서 김 가지(노드/브랜치)를 찾습니다.
  • 바로 찾았죠?
  • 그 하위 노드를 다 꺼내서 모든 페이지, X번줄 데이터를 다 합치면 그게 검색 결과 입니다.
• 왜?
  • 처음부터 데이터를 잘 정리해서 모아 두었기 때문에
  • 김 을 찾으면 김 노드 이하만 보면 되기 때문에 전체 데이터를 안봐도 됩니다. (Full-Scan을 안해도 됩니다.)
  • 즉, 봐야할 갯수를 확 줄여버려서 빨라집니다.
• 김가 를 찾는다면?
  • 김 으로 찾고, 김가 를 그 안에 또 찾으면 되죠.
  • 찾는 행위는 딱 2번 입니다.
• 이렇게 한번 찾는 행위를 몇번 하냐에 따라 복잡도를 말할 수 있는데요.
• 시간 복잡도 라는 개념으로 이 B-Tree 는 O(logN) 으로 표현 합니다. (시간복잡도는 따로 알아보세요~!)

김씨가 너무 많으면?

• 사실 B-Tree 는 한 가지에서 하위의 가지 숫자를 제한 함으로써, 특정 데이터만 너무 오래 걸릴 수 있는 문제를 해결 합니다.
  
• 위 예시는 이해를 위해 쉽게 표현 했으며, 실제로 위처럼 간단히 저장하진 않아요.
• 그래도 나름 제약을 통해 해결을 한다. 결국 시간복잡도는 똑같이 O(logN)이다 라는 것만 기억하세요.

B-Tree 의 단점

예상 하셨듯이, 저장될 때마다 B-Tree 를 갱신 해야 합니다.

여기서 비용이 발생 하죠. (정렬하고, 하위 가지 찾아서 업데이트 하고…)

그래도 키를 알고 있고, 이때 어디 가지에 업뎃 하면 되는지도 아니까

엄청난 비용 까지는 아닙니다.

또한, 복잡한 구조상 구현이 다소 까다롭습니다.

그러나 우리가 직접 B-Tree 알고리즘을 코드로 구현할 일은 거의 없으니 안심하세요.

DB가 인덱스 알고리즘으로 B-Tree 를 쓰는 이유

목적에 잘 맞기 때문 입니다.

• DB의 인덱스는 특정 키를 통해 빠르게 데이터를 찾기 위함 입니다.
• 결국 B-Tree 와 목적이 같죠.
• 또하나, B-Tree 는 위 특정에 의해 순서대로 모여 있게 됩니다. 고로 범위검색 (예: 가~다, 10~100)에도 굉장히 효율적 입니다. 시작단어와 끝단어 사이의 모든 가지를 가져오면 되니까요.

prefix 검색만 인덱스를 타는 이유

이제 B-Tree 의 동작 구조를 이해 했다면, 당연하게 느껴질 겁니다.

B-Tree는 시작글자를 기준으로 찾아나가기 때문에요.

김** 을 찾는건 무지 쉽지만, *형* 은 찾을수가 없어요.

DB에 보면 LIKE '%키워드%' 라는 형태의 SQL 이 있는데요.

LIKE 구문은 그래서 인덱스를 타지 못해 무지하게 느립니다.

그럼 LIKE 는 어떻게 찾냐고요? → FULL SCAN 이죠 네, 엄청 느린 이유 입니다.

하지만 LIKE 라 하더라도요. prefix 검색은 인덱스를 탑니다.

LIKE '김%'같은 것 말이지요. 이유는 아시겠죠?

근데 저는, suffix 검색을 빠르게 하고 싶어요?

B-Tree 는 정방향으로 정렬되어 있다보니, ~로 끝나는 검색은 어렵겠죠?

그런데, 실무 요구사항은 항상 있기 마련이죠.

이때, B-Tree 사용성을 깨지 않고도 좋은 방법이 있습니다.

바로, 그냥 뒤집어서 저장하는거에요.

예를 들어, ABC 가 있으면 CBA 로 저장하고

찾을 때도 뒤집어서 찾으면 됩니다. 참~쉽죠?

(그런데, 실전에서는 이렇게 뒤집기 보다는, 인덱스 정렬 방식만 뒤집어 별도의 인덱스를 만드는 방법을 더 많이 사용 합니다.)

LIKE %검색어% 를 빠르게 하려면

FULLTEXT 검색을 써야 합니다.

이것은 결국 원본 데이터에서 키워드를 추출하여 Key-Value Store 에 키를 넣는것과 같습니다.

ElasticSearch 가 정확히 이 역할을 하죠.

Mysql 도 FULLTEXT 검색 기능이 있습니다.

그러나, 이것은 단어의 의미를 알아야 키워드를 추출 할텐데 (토크나이저)

한글을 지원하지 않아 한국에서 잘 쓰지 않을 뿐, 영어권에서는 쉽게 사용 합니다.

(요즘은 FULLTEXT에 한글 형태소 분석 Plugin 도 있기는 합니다.)

마무리

오늘은 다소 글이 길었죠?

아무래도 너무 어려운 주제라, 여러 예시가 많아 그런 것 같습니다.

B-Tree 알고리즘을 잘 이해한다면,

여러분의 DB 사용 능력, 결국 성능을 고려한 SQL 작성 능력이 더 커질 수 밖에 없습니다.

이 Query가 어떤 식으로 동작할지 알기 때문이죠.

앞으로도 좋은 글로 찾아올께요.

행복한 하루 되십시오.

매튜 드림.