반응형 ALL88 확장성 해싱(Extendible Hashing) 확장성 해싱은 동적인 데이터 저장을 위해서 주로 사용합니다. 따라서, 안정적인 자체 재배열을 지원하는 파일구조를 필요로합니다. 데이터 사이즈가 동적으로 변하기때문에, 정적 해싱에는 부적합합니다. 정적 해싱이란, 고정된 크기의 해시 공간을 확보하여 진행하고, 동적 해싱은 동적으로 해시 공간을 확장 혹은 축소하여 진행합니다. 확장성 해싱에는 Tries (Radix Searching)을 사용합니다. 분기 노드와 정보 노드를 가지고, 마지막에 위치한 정보 노드에만 실제 데이터가 존재합니다. 그 중에서도 분기점이 적은 Radix 2 trie를 사용합니다. (즉, Binary를 사용) 셀 주소와 셀의 배열로 이루어진 디렉토리로 데이터 버킷을 연결합니다. Overflow가 발생하게 되면, 버킷을 Split하게 되는데.. 2024. 3. 20. Hashing(해싱) 해싱은 파일의 접근을 O(1)로 보장해주는 자료구조입니다. Hash Function을 통해 받은 해시값으로 매핑하여 사용하게됩니다. 이때, 해시함수 값이 같은 두 개 이상을 동의어(Synonyms) 라고 합니다. 동의어가 아예 나오지 않게끔 완벽한 해싱 알고리즘은 극히 어려워서 사실상 충돌이 일어날 수 밖에 없습니다. 그렇다면 충돌을 줄이는 방법밖에 없는데 이를 위해선 다음 3가지 방법을 고려할 수 있습니다. 레코드 분산 저장 추가 메모리 공간 사용 각 주소 공간에 하나 이상의 레코드 저장 (버킷 방식) 우선 해시 알고리즘에 대해서 서술하겠습니다. 해시 알고리즘은 다음과 같은 방법들이 존재합니다. 키 패턴 분석 키 일부를 포갬 나누기 (주로 소수로 나눗셈) 키를 제곱 후 중간 부분을 주소로 취함 진법 변.. 2024. 3. 20. 키 순차접근 및 B+ Tree 인덱스화된 순차 접근은 2가지 방법으로 이루어 집니다. Index 방식 Sequential 방식 인덱스 방식은 키로 인덱스를 통한 직접 검색(Exact Search)를 수행합니다. 순차방식은 키의 순서대로 레코드들을 순차적으로 접근(Range Search) 합니다. 하지만, 기존의 단순 인덱스(Simple Index) 혹은 B-Tree는 순차접근을 위해서 중위순회(In-order Travers)를 요구하기 때문에 순차접근에 불리합니다. (제일 처음을 찾아서 내려온다음, 부모노드, 오른쪽 자식 노드, 다시 상위노드 ... 을 수행하기 때문에 많은 시간 소요) 이를 해결하기 위해 레코드 삽입, 삭제 후에도 키 순서대로 레코드들이 물리적으로 저장되는 집합체인 순차 집합(Sequential Set)을 사용합니다.. 2024. 3. 18. B* Tree와 Node Buffering B* Tree는 2-3 Split 방식으로 운용됩니다. 2-3 Split은 재분배 우선 삽입일 때, split 시 각 노드는 1/2가 아닌 2/3이 찬 상태일때 수행합니다. B* Tree는 다음으로 정의할 수 있습니다. 모든 노드는 최대 m개의 자손 노드를 가집니다. 루트 노드를 제외한 모든 노드는 최소 ceil((2m - 1) / 3) 개의 자손 노드를 가집니다. 루트 노드는 최소 2개의 자손 노드를 가집니다. 모든 단말 노드는 동일 레벨입니다. 2-3 Split을 사용한 B* Tree는 다음 2가지의 문제점을 가집니다. 루트 노드는 이웃 노드가 없으므로 2-3 Split이 불가능 합니다. 루트 노드는 2/3 이상의 자손 노드를 가질 수 없습니다. 1번째 문제의 경우 루트 노드 사이즈를 다른 노드들 보.. 2024. 3. 18. 이전 1 2 3 4 5 6 ··· 22 다음 반응형