실제 DB의 인덱싱은 B+트리로 이루어져있다. 다음 그림은 인덱싱을 나타낸 것이다. 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능이다. 실제 DB의 인덱싱은 B+트리로 이루어져있다. 다음 그림은 인덱싱을 나타낸 것이다. 인덱싱은 어떠한 자료를 찾는데 key값을 이용해 효과적으로 찾을 수 있는 기능이다. B+트리에는 리프노드에 새로운 data값들이 들어가 있다. B트리의 경우에는 편의상 data를 생략하여 그렸지만, 각 key값이 data를 가지고 있었다고 생각하면 된다. 그럼 B트리와 B+트리 달라진 점에 대해서 알아보자. 모든 key, data가 리프노드에 모여있다. B트리는 리프노드가 아닌 각자 key마다 data를 가진다면, B+트리는 리프 노드에 모든 data를 가..

B-TREE B트리는 이진트리에서 발전되어 모든 리프노드들이 같은 레벨을 가질 수 있도록 자동으로 벨런스를 맞추는 트리다. 또한 정렬된 순서를 보장하고, 멀티레벨 인덱싱을 통한 빠른 검색을 할 수 있기 때문에 DB에서 사용하는 자료구조 중 한 종류이다. 실제 DB에서는 B트리에서 발전한 B+트리를 실제로 사용한다. 다음은 차수가 3인 B트리다. 파란색 부분은 각 노드의 key를 나타내며, 빨간색 부분은 자식 노드들을 가르키는 포인터다. key들은 노드 안에서 항상 정렬된 값을 가지며, 이진검색 트리처럼 각 key들의 왼쪽 자식들은 항상 key보다 작은 값을, 오른쪽은 큰 값을 가진다. B트리는 이진트리와 다르게 하나의 노드에 많은 수의 정보를 가지고 있을 수 있다. 최대 M개의 자식을 가질 수 있는 B트..

트라이(Trie)의 형태 Trie: 트라이(Trie)란 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조 위에 보이는 트리의 루트에서부터 자식들을 따라가면서 생성된 문자열들이 트라이 자료구조에 저장되어 있다고 볼 수 있다. 저장된 단어는 끝을 표시하는 변수를 추가해서 저장된 단어의 끝을 구분할 수 있다. DFS 형태로 검색을 해보면 사진의 번호에 나와있듯이 to, tea, ted, ten, A, i, in, inn이라는 단어들이 자료구조에 들어가 있음을 알 수 있다. 트라이(Trie)의 예시 주황색으로 된 노드들이 입력된 문자열들이다. 현재 be, bee, can, cat, cd가 들어가 있다 사용목적 목적 문자열의 탐색을 하고자 할 때 시간 복잡도를 보면 알 수 있다. 단순하게 하나씩 비..

해시 데이터를 효율적으로 관리하기 위해, 임의의 길이 데이터를 고정된 길이의 데이터로 매핑하는 것 해시 함수를 구현하여 데이터 값을 해시 값으로 매핑한다. 장점(Advantage)과 단점(Disadvantage) ● 해싱된 키(Hash Key)를 가지고 배열의 인덱스로 사용하기 때문에 삽입, 삭제, 검색이 매우 빠르다. ● 해시 함수(Hash Function)를 사용하는데 추가적인 연산이 필요하다. ● 적은 데이터 저장 시 구현 방식에 따라 연결 리스트(Linked List)를 사용하는 경우 오버 헤드의 부담이 생기고, 캐시 효율이 떨어진다. ● 해시 테이블(Hash Table)의 크기가 유한적이고 해시 함수(Hash Function)의 특성상 해시 충돌(Hash Collision)이 발생할 수밖에 없다..

이진트리 이진트리는 모든 노드가 정확하게 두 개의 서브 트리를 가지고 있는 트리이다. 다만 서브 트리는 공백이 될 수 있다. 즉 노드의 유한 집합으로서 공백이거나 루트와 두 개의 분리된 이진트리인 경우 왼쪽 서브 트리와 오른쪽 서브 트리로 구성된다. 여기서 중요한 점은 왼쪽과 오른쪽 서브 트리를 확실하게 구분한다는 것이다. 일반적인 트리에서 두 개의 트리는 같지만 이진트리에서는 두 개의 트리는 다른 트리이다. 이는 이진트리에서는 서브 트리의 위치가 다르기 때문이다. 1) 편향 이진트리(skewed binary tree) 편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에 왼편으로 편향되어 있거나 반대로 모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있어야 한다. 2) 포화 이진트리(f..

힙(Heap) 힙 자료구조는 완전 이진 트리를 기초로 하는 자료구조이다. 완전 이진트리는 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리를 말한다. 그림과 같은 형태를 띄고 있으며, 몇가지 특징들을 가지고 있다. 힙은 최대힙(Max heap)과 최소힙(Min Heap)으로 나눠진다. 최대힙은 부모노드의 값이 자식노드들의 값보다 항상 크고, 최소힙은 부모노드의 값이 자식노드의 값보다 항상 작다. (위 그림은 최대힙의 예시) 이러한 성질 때문에 항상 느슨한 정렬상태(반정렬 상태)를 유지한다. 힙은 중복값을 허용한다. 힙은 최댓값 또는 최솟값을 쉽게 뽑기 위한 자료구조 임으로 중복을 허용한다. 힙을 배열로 구현 힙은 대체적으로 배열로 구현된다. 완전이진트리를 기본으로 하기 때문에 비어있는 공간이 없..