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

완전탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다. 이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답만을 출력한다. 문제를 풀 때 가장 간단한 방법이지만 모든 경우를 다 확인하기 때문에 가장 시간이 많이 소모되는 방법이다. - 일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에 특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다. - 알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다. - 선형 구조를 전체적으로 탐색하는 순차 탐색, 비선형 구조를 전체적으로 탐색하는 깊이 우선 탐색(DFS, Depth First Search)과 너비 우선 탐색(BFS, ..

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

Index란? records의 특정 data를 기준으로 빠르게 검색을 할 수 있게 records를 구조화하는 것 원하는 데이터를 빠르게 찾을 수 있게 색인을 하는 것 실제 data(record)는 정렬이 되어 있을 수도 있고, 안되있을 수도 있다. 구성 : 탐색 키(rid) + 실제 레코드를 가리키는 포인터 (Data record with key value k) 장점 : 원하는 data(record)를 쉽게 찾을 수 있다. 단점 index 를 위한 공간이 필요하다. 새로운 data를 추가, 삭제, 변경 시 이에 상응되는 인덱스 추가, 삭제, 변경이 필요할 수 있다.(거의 대부분 필요하다.) Types of Indexes single level index composite index multi level ..

트라이(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)이 발생할 수밖에 없다..