해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법에 있어서,

오버플로우(Overflow)된 리프 노드(Leaf Node)가 새롭게 발생하면, 전체 리프 노드 수에 대한 오버플로우된 리프 노드 수의 비율을 계산하여 상기 계산값이 미리 정하여진 임계값을 초과하는지 여부를 판단하는 제 1 단계와;

상기 제 1 단계에서의 판단 결과, 임계값을 초과하면, 디렉토리의 분할을 수행하고, 임계값을 초과하지 아니하면, 리프 노드 뒤에 새로운 오버플로우 노드를 연결시키는 제 2 단계를 포함하여 이루어진 것을 특징으로 하는 확장 해슁 디렉토리 분할 시점 제어 방법

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 이용한 엔트리(Entry) 삽입 방법에 있어서,

삽입하려는 엔트리를 해슁 함수를 사용하여 디렉토리 크기 만큼의 비트로 된 디렉토리의 인덱스를 계산한 후, 상기 계산한 디렉토리의 인덱스에 연결된 버켓(홈 버켓 : Home Bucket)에 오버플로우 버켓이 존재하는지 여부를 판단하는 제 1 단계와;

제 2 항에 있어서,

제 2 항에 있어서,

상기 제 2 단계는,

상기 홈 버켓에 엔트리가 삽입 가능하면, 상기 홈 버켓에 엔트리를 삽입하는 서브 단계를 더 포함하여 이루어진 것을 특징으로 하는 디렉토리 분할 시점을 이용한 엔트리 삽입 방법

제 2 항에 있어서,

상기 제 2 단계에서의 판단 결과, 지역 깊이가 전역 깊이보다 크거나 같으면, 상기 제 6 단계로 진행하는 것을 특징으로 하는 디렉토리 분할 시점을 이용한 엔트리 삽입 방법

제 2 항에 있어서,

상기 제 4 단계에서의 판단 결과, 새로 연결된 홈 버켓에 엔트리를 삽입할 수 있으면, 상기 홈 버켓에 엔트리를 삽입하는 제 9 단계를 더 포함하여 이루어진 것을 특징으로 하는 디렉토리 분할 시점을 이용한 엔트리 삽입 방법

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 이용한 엔트리(Entry) 삭제 방법에 있어서,

삭제할 엔트리가 들어 있을 디렉토리 인덱스를 계산하기 위하여 삭제할 엔트리를 해슁하고, 상기 디렉토리 인덱스에 연결되어 있는 버켓에서 삭제할 엔트리의 위치를 찾은 후, 상기 삭제할 엔트리가 있는 버켓에 연결되어 있는 마지막 버켓을 찾아서, 상기 삭제할 엔트리가 마지막 버켓의 마지막 엔트리인지 여부를 판단하는 제 1 단계와;

상기 제 1 단계에서의 판단 결과, 마지막 버켓의 마지막 엔트리가 아니면, 상기 삭제할 엔트리의 위치에 마지막 버켓의 마지막 엔트리를 넣고, 마지막 버켓의 마지막 엔트리에 NULL을 넣은 후, 마지막 버켓에 언더플로우가 발생하는지 여부를 판단하는 제 2 단계와;

상기 제 2 단계에서의 판단 결과, 언더플로우가 발생하면, 언더플로우가 발생한 디렉토리 인덱스에 연결된 오버플로우 버켓이 존재하는지 여부를 판단하여, 오버플로우 버켓이 존재하면, 마지막 버켓에 엔트리가 존재하는지 여부를 판단하는 제 3 단계와;

상기 제 3 단계에서의 판단 결과, 마지막 버켓에 엔트리가 존재하면, 종료하고, 마지막 버켓에 엔트리가 존재하지 아니하면, 마지막 버켓을 반환한 후, 상기 반환한 버켓이 홈 버켓에 연결된 오버플로우 버켓인지 여부를 판단하는 제 4 단계와;

상기 제 4 단계에서의 판단 결과, 오버플로우 버켓이면, 오버플로우된 리프 노드의 수를 하나 감소시킨 후, 종료하는 제 5 단계를 포함하여 이루어진 것을 특징으로 하는 디렉토리 분할 시점 제어 방법을 이용한 엔트리 삭제 방법

제 7 항에 있어서,

상기 제 3 단계는,

오버플로우 버켓이 존재하지 아니하면, 병합할 디렉토리 인덱스를 계산하여, 상기 계산된 디렉토리 인덱스를 기준으로 언더플로우가 발생한 버켓인지 여부를 판단하는 제 1 서브 단계와;

상기 제 1 서브 단계에서의 판단 결과, 언더플로우가 발생한 버켓이 아니면, 홈 버켓의 수를 하나 감소시키고, 디렉토리에 연결된 홈 버켓에 있는 엔트리를 언더플로우가 발생한 버켓에 넣은 후, 홈 버켓을 반환하며, 상기 인덱스에 언더플로우가 발생한 버켓을 연결시키고, 상기 제 1 서브 단계로 복귀하는 제 2 서브 단계를 포함하여 이루어진 것을 특징으로 하는 디렉토리 분할 시점 제어 방법을 이용한 엔트리 삭제 방법

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 이용한 엔트리(Entry) 검색 방법에 있어서,

해슁 함수를 이용하여 디렉토리의 인덱스를 계산한 후, 상기 디렉토리에 연결된 버켓을 노드(Node)로 지정하는 제 1 단계와;

상기 제 1 단계에서 지정된 노드에 엔트리가 존재하는지 여부를 판단하는 제 2 단계와;

상기 제 2 단계에서의 판단 결과, 엔트리가 존재하고, 검색하고자 하는 키 값과 노드에 있는 엔트리의 키 값이 같으면, 상기 엔트리의 주소를 저장하는 제 3 단계를 포함하여 이루어진 것을 특징으로 하는 디렉토리 분할 시점 제어 방법을 이용한 엔트리 검색 방법

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 실행시킬 수 있는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체에 있어서,

오버플로우(Overflow)된 리프 노드(Leaf Node)가 새롭게 발생하면, 전체 리프 노드 수에 대한 오버플로우된 리프 노드 수의 비율을 계산하여 상기 계산값이 미리 정하여진 임계값을 초과하는지 여부를 판단하는 제 1 단계와;

상기 제 1 단계에서의 판단 결과, 임계값을 초과하면, 디렉토리의 분할을 수행하고, 임계값을 초과하지 아니하면, 리프 노드 뒤에 새로운 오버플로우 노드를 연결시키는 제 2 단계를 포함하여 실행시킬 수 있는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 이용한 엔트리(Entry) 삽입 방법을 실행시킬 수 있는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체에 있어서,

삽입하려는 엔트리를 해슁 함수를 사용하여 디렉토리 크기 만큼의 비트로 된 디렉토리의 인덱스를 계산한 후, 상기 계산한 디렉토리의 인덱스에 연결된 버켓(홈 버켓 : Home Bucket)에 오버플로우 버켓이 존재하는지 여부를 판단하는 제 1 단계와;

상기 제 1 단계에서의 판단 결과, 오버플로우 버켓이 존재하지 아니하면, 상기 홈 버켓에 엔트리가 삽입 가능한지 여부를 판단하여, 삽입 가능하지 아니하면, 지역 깊이(Local Depth)가 전역 깊이(Global Depth)보다 더 작은지 여부를 판단하는 제 2 단계와;

상기 제 2 단계에서의 판단 결과, 홈 버켓의 깊이가 디렉토리 깊이보다 더 작으면, 두 개의 버켓을 새로 할당받아 홈 버켓에 있는 엔트리를 재해슁하여 나누어 넣는 제 3 단계와;

상기 제 2 단계에서의 판단 결과, 홈 버켓의 깊이가 디렉토리 깊이와 같으면, 새로 연결된 홈 버켓에 엔트리를 삽입할 수 있는지 여부를 판단하여, 엔트리를 삽입할 수 없으면, 새로운 버켓을 할당받아 엔트리를 삽입한 후, 홈 버켓에 연결하고, 오버플로우된 리프 노드의 수를 하나 증가시키는 제 4 단계와;

홈 버켓의 수와 상기 제 4 단계에서 증가시킨 오버플로우된 리프 노드의 수의 비율을 계산하여 미리 지정한 임계값을 초과하여 디렉토리를 확장하여야 하면, 오버플로우 문제가 해결될 때까지, 오버플로우가 발생한 버켓을 제외하고는 모든 홈 버켓을 가리키는 디렉토리 엔트리가 두 배가 되도록 한 후, 오버플로우가 발생한 버켓은 두 개의 버켓에 엔트리를 분배하는 제 5 단계를 포함하여 이루어진 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 이용한 엔트리(Entry) 삭제 방법을 실행시킬 수 있는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체에 있어서,

삭제할 엔트리가 들어 있을 디렉토리 인덱스를 계산하기 위하여 삭제할 엔트리를 해슁하고, 상기 디렉토리 인덱스에 연결되어 있는 버켓에서 삭제할 엔트리의 위치를 찾은 후, 상기 삭제할 엔트리가 있는 버켓에 연결되어 있는 마지막 버켓을 찾아서, 상기 삭제할 엔트리가 마지막 버켓의 마지막 엔트리인지 여부를 판단하는 제 1 단계와;

상기 제 1 단계에서의 판단 결과, 마지막 버켓의 마지막 엔트리가 아니면, 상기 삭제할 엔트리의 위치에 마지막 버켓의 마지막 엔트리를 넣고, 마지막 버켓의 마지막 엔트리에 NULL을 넣은 후, 마지막 버켓에 언더플로우가 발생하는지 여부를 판단하는 제 2 단계와;

상기 제 2 단계에서의 판단 결과, 언더플로우가 발생하면, 언더플로우가 발생한 디렉토리 인덱스에 연결된 오버플로우 버켓이 존재하는지 여부를 판단하여, 오버플로우 버켓이 존재하면, 마지막 버켓에 엔트리가 존재하는지 여부를 판단하는 제 3 단계와;

상기 제 3 단계에서의 판단 결과, 마지막 버켓에 엔트리가 존재하면, 종료하고, 마지막 버켓에 엔트리가 존재하지 아니하면, 마지막 버켓을 반환한 후, 상기 반환한 버켓이 홈 버켓에 연결된 오버플로우 버켓인지 여부를 판단하는 제 4 단계와;

상기 제 4 단계에서의 판단 결과, 오버플로우 버켓이면, 오버플로우된 리프 노드의 수를 하나 감소시킨 후, 종료하는 제 5 단계를 포함하여 이루어진 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체

해쉬 인덱스(Hash Index) 구조의 확장 해슁(Extendible Hashing) 디렉토리(Directory) 분할 시점 제어 방법을 이용한 엔트리(Entry) 검색 방법을 실행시킬 수 있는 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체에 있어서,

해슁 함수를 이용하여 디렉토리의 인덱스를 계산한 후, 상기 디렉토리에 연결된 버켓을 노드(Node)로 지정하는 제 1 단계와;

상기 제 1 단계에서 지정된 노드에 엔트리가 존재하는지 여부를 판단하는 제 2 단계와;

상기 제 2 단계에서의 판단 결과, 엔트리가 존재하고, 검색하고자 하는 키 값과 노드에 있는 엔트리의 키 값이 같으면, 상기 엔트리의 주소를 저장하는 제 3 단계를 포함하여 이루어진 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록 매체