반응형 ALL88 B-Tree (2) 앞선 포스트에서 설명한 B-Tree에 이어 서술합니다. B-Tree의 자손노드는 B-Tree의 가장 하단의 노드 레벨로, B-Tree의 단말 레벨의 +1값과 동치입니다. 자손노드의 특징으로는, Root 노드와 단말 노드 이외의 모든 노드들은 ceil(m/2) 개의 자손 노드를 가진다는 특징이 있습니다. B-Tree에서 중복을 없애기 위해 B-Tree 각 노드에 키와 데이터 레코드에 대한 주소를 포함합니다. 이 방법을 사용하여 중복을 방지하고 공간을 절약하며, 검색시간을 단축하지만 내부 노드의 크기가 증가하는 단점을 포함합니다. B-Tree의 특성을 정리하자면 다음과 같습니다. 모든 노드는 최대 m개의 자손 노드를 가집니다. 루트와 단말 노드 이외의 모든 노드는 최소 ceil(m/2)개 이상의 자손노드를 .. 2024. 3. 12. B-Tree 앞선 포스트에서 서술한 단점들을 해결하기 위해 사용하는 구조로 B-Tree가 있습니다. B-Tree는 노드의 사이즈가 K라고 가정할 때, 탐색시간이 logkN에 비례하기 때문에 빠른 속도를 위해 사용합니다. B-Tree를 사용하면, 인덱스 탐색시 이진탐색보다 빠르며, 삽입 및 삭제를 할 때 또한 탐색만큼 빠른 속도가 유지되어서 채택합니다. B-Tree에 앞서 다른 자료구조들과 그것들의 문제점을 서술하겠습니다. 먼저 이진탐색트리 (Binary Search Tree)입니다. 이진탐색트리는 Linked 구조로 구성되며, 정렬이 필요없습니다. 하지만, 디스크에 저장된 인덱스에 대해서는 빠른 속도를 보장할 수 없고, 트리의 효율적인 밸런스 유지가 어렵습니다. 즉 Skewed Tree 형태가 나오기 쉽기 때문에 A.. 2024. 3. 12. 키 정렬과 인덱싱 앞선 포스팅에서 이진탐색을 위해서 키를 정렬해야하는데, 정렬된 레코드 파일을 생성할 때까지 디스크 I/O를 두번 수행하게 됩니다. 하지만, 이렇게 정렬해 두어도 Random Access 방식에서는 클러스터를 무작위로 찍어서 접근하므로, 실린더를 누비는 상황이 생길 수 있습니다. 이 경우 탐색 시간이 증가하는 문제가 발생합니다. 따라서, RAM에 가져온 RRN과 탐색을 위한 레코드 일부를 인덱스 파일로 RAM에 저장해둡니다. 이 때, 베이스가 되는 파일은 정렬이 되지 않아도 되지만, 인덱스 파일은 정렬상태로 유지합니다. 이렇게 할 경우, RAM에 있는 인덱스 파일의 정렬은 O(N log N)이 소요되지만 RAM은 충분히 빠르기 때문에 이 상태로 RAM에서 선형 탐색을 통해 빠르게 접근할 수 있습니다. 그러.. 2024. 3. 11. 레코드의 관리 레코드들을 식별하기 위해서 레코드 필드 값에 기반한 레코드 키를 생성합니다. 키는 다음 2가지로 구분됩니다. 주 키 (Primary Key) 보조 키 (Secondary Key) 주 키는 응용프로그램 환경에서 주로 사용될 키이고, 보조 키는 이름대로 보조 수단의 키이며 주 키에서 가지는 필요조건 중 유일성이 중요하지 않습니다. 키의 필요 조건은 다음 2가지입니다. 유일성 (Uniqueness) 희소성 (Minimality) 유일성은 하나 이상의 필드의 조합으로 유일하게 레코드를 식별할 수 있음을 의미합니다. 희소성은 유일성을 만족시키는 최소개수의 필드 조합을 의미합니다. 키를 선택할 때는 다음 3가지 조건을 만족해야합니다. 유일성 (Uniqueness) 데이터 포함 X (Dataless) 지속성 (Per.. 2024. 3. 11. 이전 1 2 3 4 5 6 7 ··· 22 다음 반응형