18장 : B-트리 (B-Tree) 검색

검색을 위한 자료구조 중에서 잠재력이 가장 큰 것은 이진 트리입니다.  비록 하나의 부모가 두개의 자식밖에 가지질 못하고,  자칫 균형이 맞지 않으면 검색 효율이 선형검색 급으로 떨어지긴 하지만요. 

그렇지만 이진 트리는 구조의 간결함과 균형만 맞다면 검색, 삽입, 삭제 모두 O(logN)의 성능을 보이는 장점이 있어서,  이를 바탕으로 개선하고자 하는 노력이 많이 있어 왔습니다.

그 중에서도 이번 장에서는 두마리의 토끼를 모두 잡은 B-트리에 대해 알아봅니다. 

17장 : 기수 검색 (Radix Search)

컴퓨터의 두뇌인 CPU의 동작을 쪼개어 들어가 보면 결국 0과 1 즉 비트(bit)를 다루는 것을 기본으로 합니다.  컴퓨터에 저장된 모든 데이터는 비트의 배열로 구성됩니다.  하나의 바이트는 8개의 비트로 구성되며,  일반적인 정수형은 4개의 바이트 즉 32비트로 구성됩니다.

지금까지는 데이터를 수학적인 혹인 추상적인 개념으로서 취급했다면, 이 장에서 소개하는 기수 검색(Radix Search)은 데이터를 기본 단위인 비트의 배열로 취급합니다.  비트는 0과 1 두가지 값 밖에 없기 때문에 자연스럽게 자식을 두개 가질 수 있는 이진트리(Binary Tree)와 연결됩니다.

16장 : 해쉬 (Hash)

지금까지 배웠고 또 앞으로 배울 검색 알고리즘들은 모두 자료수 N이 커지면 검색 시간도 더 걸리는 성능을 보여줍니다.  또한 이것이 자연스럽습니다.  이들 알고리즘들은 O(N) 혹은 O(logN)의 성능을 보여 줍니다.

그런데 오늘 배울 검색 알고리즘인 해쉬(Hash)는 자료수 N과 무관하게 일정한 검색 성능을 보여줍니다.  O(1)의 성능입니다.  실로 놀라운 검색 알고리즘입니다.  그런데 알고보면 그 원리는 매우 간단합니다.

입력된 자료가 수치형이든, 스트링이든, 복합 데이터 타입이든 그것을 정수로 변환하는 함수만 정의하면 됩니다.  이 함수를 해쉬 함수라 하며, 입력 자료를 해쉬 함수에 넣어 나온 결과를 해쉬값이라고 합니다.

입력자료에 대해 고른 분포의 해쉬값이 나오는 해쉬함수가 있다면 매우 효율이 높은 해쉬 검색을 구현할 수 있습니다.  하지만 이런 이상적인 경우는 현실에 존재하지 않기 때문에 다른 입력자료가 같은 해쉬값이 나오는 경우가 빈번하게 발생합니다.

15장 : 이진트리 검색 (Binary Tree Search)

가족계획처럼 자식을 둘 이하만 가질 수 있는 이진트리(Binary Tree)는 단촐한 구성 때문에 컴퓨터 알고리즘에서 단골로 등장합니다.  단순화된 이진트리로 알고리즘을 정립한 뒤에 더 복잡한 트리에 적용하는 전략도 많이 쓰입니다.

이번 장에서는 이진트리를 효율적인 검색 구조로 사용하는 방법에 대해서 알아봅니다.  이상적이라면 이진트리의 좌우 균형이 맞아 검색의 효율이 매우 좋습니다.  하지만 이진트리를 구축하는 방법에 따라 균형이 맞지 않을 수 있는데 이때는 검색의 효율이 매우 떨어집니다.