맞춤기술찾기

홈으로 가기
맞춤기술찾기
이전대상기술
프린트하기

이전대상기술

해시 인덱스 구성 방법과 그 장치, 및 상기 장치를 구비하는 데이터 저장 장치, 및 상기 방법을 구현하는 프로그램이 기록된 기록매체

  • 기술번호 : KST2014009025
  • 담당센터 : 서울서부기술혁신센터
  • 전화번호 : 02-6124-6930
상담신청 PDF 받기
요약, Int. CL, CPC, 출원번호/일자, 출원인, 등록번호/일자, 공개번호/일자, 공고번호/일자, 국제출원번호/일자, 국제공개번호/일자, 우선권정보, 법적상태, 심사진행상태, 심판사항, 구분, 원출원번호/일자, 관련 출원번호, 기술이전 희망, 심사청구여부/일자, 심사청구항수의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 서지정보 표입니다.
요약 본 발명은 소용량 데이터의 작은 쓰기 횟수를 감소시켜 메모리 칩을 이용하는 데이터 저장 장치(ex. SSD)에 적용할 수 있는 해시 인덱스 구성 방법과 그 장치, 및 상기 장치를 구비하는 데이터 저장 장치, 및 상기 방법을 구현하는 프로그램이 기록된 기록매체를 개시한다. 본 발명은 (a) 선형 해싱을 통해 확보된 메모리 공간에 쓰기 버퍼를 할당하는 단계; (b) 할당된 쓰기 버퍼에 데이터 처리 요청에 대한 인덱스 작업 레코드 그룹을 생성하는 단계; (c) 적어도 하나의 버킷을 추출하며, 생성된 인덱스 작업 레코드 그룹을 추출된 버킷으로 출력시키는 단계; 및 (d) 생성된 인덱스 작업 레코드 그룹을 포함하는 버킷을 기반으로 하는 해시 인덱스를 구성하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법을 제공한다. 본 발명에 따르면, SSD와 같은 데이터 저장 장치의 쓰기 효율을 향상시킬 수 있으며, 그 수명도 연장시킬 수 있다.해시 인덱스(hash index), SSD, 플래시 메모리(flash memory), 버킷(bucket), 선형 해싱(linear hashing), 인덱스 작업 레코드(Index Task Record), 분할 연기(deferred splitting), 오버플로우 버킷(overflow bucket)
Int. CL G06F 17/10 (2006.01) G06F 9/00 (2006.01) G06F 12/00 (2006.01) G06F 9/44 (2006.01)
CPC G06F 16/2255(2013.01) G06F 16/2255(2013.01) G06F 16/2255(2013.01) G06F 16/2255(2013.01) G06F 16/2255(2013.01) G06F 16/2255(2013.01) G06F 16/2255(2013.01) G06F 16/2255(2013.01)
출원번호/일자 1020090003339 (2009.01.15)
출원인 연세대학교 산학협력단
등록번호/일자 10-1123335-0000 (2012.02.27)
공개번호/일자 10-2010-0083976 (2010.07.23) 문서열기
공고번호/일자 (20120328) 문서열기
국제출원번호/일자
국제공개번호/일자
우선권정보
법적상태 등록
심사진행상태 수리
심판사항
구분 신규
원출원번호/일자
관련 출원번호
심사청구여부/일자 Y (2009.01.15)
심사청구항수 19

출원인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 출원인 표입니다.
번호 이름 국적 주소
1 연세대학교 산학협력단 대한민국 서울특별시 서대문구

발명자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 발명자 표입니다.
번호 이름 국적 주소
1 박상현 대한민국 서울특별시 송파구
2 노홍찬 대한민국 서울특별시 강북구
3 이지원 대한민국 서울특별시 서대문구

대리인

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 대리인 표입니다.
번호 이름 국적 주소
1 특허법인우인 대한민국 서울특별시 강남구 역삼로 ***, *층(역삼동, 중평빌딩)

최종권리자

번호, 이름, 국적, 주소의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 인명정보 - 최종권리자 표입니다.
번호 이름 국적 주소
1 연세대학교 산학협력단 서울특별시 서대문구
번호, 서류명, 접수/발송일자, 처리상태, 접수/발송일자의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 행정처리 표입니다.
번호 서류명 접수/발송일자 처리상태 접수/발송번호
1 [특허출원]특허출원서
[Patent Application] Patent Application		 2009.01.15 수리 (Accepted) 1-1-2009-0026820-34
2 선행기술조사의뢰서
Request for Prior Art Search		 2009.11.04 수리 (Accepted) 9-1-9999-9999999-89
3 선행기술조사보고서
Report of Prior Art Search		 2009.12.08 수리 (Accepted) 9-1-2009-0067656-01
4 의견제출통지서
Notification of reason for refusal		 2010.09.17 발송처리완료 (Completion of Transmission) 9-5-2010-0413592-56
5 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2010.11.16 수리 (Accepted) 1-1-2010-0747952-32
6 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2010.12.15 수리 (Accepted) 1-1-2010-0825583-06
7 [지정기간연장]기간연장(단축, 경과구제)신청서
[Designated Period Extension] Application of Period Extension(Reduction, Progress relief)		 2011.01.17 수리 (Accepted) 1-1-2011-0036001-06
8 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2011.02.17 보정승인간주 (Regarded as an acceptance of amendment) 1-1-2011-0114362-70
9 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2011.02.17 수리 (Accepted) 1-1-2011-0114328-27
10 최후의견제출통지서
Notification of reason for final refusal		 2011.08.19 발송처리완료 (Completion of Transmission) 9-5-2011-0465470-82
11 [거절이유 등 통지에 따른 의견]의견(답변, 소명)서
[Opinion according to the Notification of Reasons for Refusal] Written Opinion(Written Reply, Written Substantiation)		 2011.10.19 수리 (Accepted) 1-1-2011-0815599-81
12 [명세서등 보정]보정서
[Amendment to Description, etc.] Amendment		 2011.10.19 보정승인 (Acceptance of amendment) 1-1-2011-0815598-35
13 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2011.12.15 수리 (Accepted) 4-1-2011-5252006-10
14 등록결정서
Decision to grant		 2012.02.16 발송처리완료 (Completion of Transmission) 9-5-2012-0090419-13
15 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2013.04.24 수리 (Accepted) 4-1-2013-5062749-37
16 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2013.06.24 수리 (Accepted) 4-1-2013-5088566-87
17 출원인정보변경(경정)신고서
Notification of change of applicant's information		 2014.09.25 수리 (Accepted) 4-1-2014-5114224-78
번호, 청구항의 정보를 제공하는 이전대상기술 뷰 페이지 상세정보 > 청구항 표입니다.
번호 청구항
1 1
(a) 주기억장치에서 쓰기 버퍼를 할당하는 단계;(b) 데이터의 처리 요청과 관련된 정보인 인덱스 작업 레코드 그룹들을 할당된 쓰기 버퍼에 기록하는 단계;(c) 상기 쓰기 버퍼에 기록된 인덱스 작업 레코드 그룹들 중에서 선택된 적어도 하나의 인덱스 작업 레코드 그룹을 해시 함수에 의해 정해진 보조기억장치의 버킷(bucket)에 기록하는 단계; 및(d) 상기 버킷에 기록된 인덱스 작업 레코드 그룹과 관련된 정보를 이용하여 상기 데이터에 대한 해시 인덱스를 구성하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
2 2
제 1 항에 있어서,상기 (c) 단계는,(ca) 상기 버킷에 기록을 수행하는 도중에 오버플로우가 발생하면, 상기 버킷이 다음 순위에 스플릿을 수행하는 차순위 스플릿 버킷인지 여부를 판별하는 단계; 및(cb) 상기 판별 결과에 따라 상기 버킷에 기록된 인덱스 작업 레코드 그룹을 상기 버킷에 체인 연결된 오버플로우 버킷 또는 다른 버킷의 스플리팅으로부터 신규 생성된 버킷에 기록하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
3 3
제 1 항에 있어서,상기 (b) 단계는,(ba) 상기 처리 요청이 수신되면 해당 데이터의 처리 형태를 표시하는 작업 타입 데이터를 생성하고, 상기 해당 데이터에 대한 인덱스 레코드를 생성하는 단계; 및(bb) 상기 생성된 작업 타입 데이터와 상기 생성된 인덱스 레코드를 결합시켜 인덱스 작업 레코드를 생성하고, 생성된 적어도 하나의 인덱스 작업 레코드를 묶어 하나의 인덱스 작업 레코드 그룹으로 하여 상기 인덱스 작업 레코드 그룹들을 상기 쓰기 버퍼에 기록하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
4 4
제 2 항에 있어서,상기 (ca) 단계에서 상기 버킷이 상기 차순위 스플릿 버킷으로 판별되면 상기 (cb) 단계는,(cba) 부하율(load factor)이 임계치 이상인지 여부를 판별하는 단계; 및(cbb) 상기 (cba) 단계에서의 판별 결과에 따라 상기 오버플로우 버킷에 기록하거나 상기 신규 생성된 버킷에 기록하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
5 5
제 4 항에 있어서,상기 (cba) 단계에서 상기 부하율이 상기 임계치 이상인 것으로 판별되면 상기 (cbb) 단계는,(cbba) 상기 차순위 스플릿 버킷을 검색하는 단계;(cbbb) 상기 검색된 차순위 스플릿 버킷에 체인 연결된 오버플로우 버킷을 모두 추출하는 단계;(cbbc) 상기 검색된 차순위 스플릿 버킷과 상기 추출된 오버플로우 버킷에 포함된 모든 인덱스 작업 레코드 그룹으로부터 동일 데이터 처리 요청을 담은 인덱스 작업 레코드를 모두 추출하는 단계;(cbbd) 추출된 인덱스 작업 레코드들과 추출되지 않고 남아있는 인덱스 작업 레코드들을 비교하여 인덱스 레코드의 키 정보가 동일한 것끼리 삭제하는 단계; 및(cbbe) 삭제되지 않고 남은 인덱스 작업 레코드들을 수집하며, 상기 수집된 인덱스 작업 레코드들을 상기 추출된 오버플로우 버킷 또는 상기 신규 생성된 버킷에 기록하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
6 6
제 4 항에 있어서,상기 (cba) 단계에서 상기 부하율이 상기 임계치 미만인 것으로 판별되면 상기 (cbb) 단계는,(cbba) 오버플로우 버킷을 생성하고, 생성된 오버플로우 버킷을 상기 버킷에 체인 연결시키는 단계; 및(cbbb) 상기 버킷에 기록된 인덱스 작업 레코드 그룹을 상기 버킷에 체인 연결된 오버플로우 버킷에 기록하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
7 7
삭제
8 8
제 2 항에 있어서,상기 (ca) 단계에서 상기 버킷이 상기 차순위 스플릿 버킷이 아닌 것으로 판별되면 상기 (cb) 단계는,(cba) 오버플로우 버킷을 생성하고, 생성된 오버플로우 버킷을 상기 버킷에 체인 연결시키는 단계; 및(cbb) 상기 버킷에 기록된 인덱스 작업 레코드 그룹을 상기 버킷에 체인 연결된 오버플로우 버킷에 기록하는 단계를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
9 9
제 1 항에 있어서,상기 (c) 단계는 상기 할당된 쓰기 버퍼가 상기 쓰기 버퍼에 기록된 인덱스 작업 레코드 그룹들로 가득 차면 크기값이 최대인 인덱스 작업 레코드 그룹부터 상기 버킷에 기록하는 것을 특징으로 하는 해시 인덱스 구성 방법
10 10
제 3 항에 있어서,상기 (bb) 단계는 미리 정해진 버킷의 크기를 고려하여 상기 인덱스 작업 레코드 그룹들을 상기 쓰기 버퍼에 기록하는 것을 특징으로 하는 해시 인덱스 구성 방법
11 11
제 1 항에 있어서,상기 (b) 단계에서 상기 쓰기 버퍼에 기록된 인덱스 작업 레코드 그룹들은 적어도 하나의 인덱스 작업 레코드를 포함하며, 상기 인덱스 작업 레코드는 입력 작업인지 또는 삭제 작업인지를 표시하는 작업 타입 데이터 및 인덱스 레코드의 키 정보를 포함하는 것을 특징으로 하는 해시 인덱스 구성 방법
12 12
제 1 항에 있어서,상기 (c) 단계는 상기 버킷으로 상기 보조기억장치에서 버킷을 검색하여 상기 검색된 버킷들 중에서 상기 선택된 인덱스 작업 레코드 그룹의 크기보다 더 큰 버킷을 이용하거나, 상기 검색된 버킷이 적어도 하나의 오버플로우 버킷과 체인 연결된 때 상기 검색된 버킷으로부터 가장 끝에 위치하는 상기 오버플로우 버킷을 이용하는 것을 특징으로 하는 해시 인덱스 구성 방법
13 13
컴퓨터로 판독 가능한 기록매체에 있어서,제 1 항 내지 제 6 항 중 어느 한 항, 또는 제 8 항 내지 제 12 항 중 어느 한 항에 따른 방법을 구현하는 프로그램이 기록된 기록매체
14 14
주기억장치에서 쓰기 버퍼를 할당하는 쓰기 할당부;데이터의 처리 요청과 관련된 정보인 인덱스 작업 레코드 그룹들을 할당된 쓰기 버퍼에 기록하는 인덱스 작업 레코드 그룹 생성부;상기 쓰기 버퍼에 기록된 인덱스 작업 레코드 그룹들 중에서 선택된 적어도 하나의 인덱스 작업 레코드 그룹을 해시 함수에 의해 정해진 보조기억장치의 버킷(bucket)에 기록하는 인덱스 작업 레코드 그룹 출력부; 및상기 버킷에 기록된 인덱스 작업 레코드 그룹과 관련된 정보를 이용하여 상기 데이터에 대한 해시 인덱스를 구성하는 해시 인덱스 구성부를 포함하는 것을 특징으로 하는 해시 인덱스 구성 장치
15 15
제 14 항에 있어서,상기 인덱스 작업 레코드 그룹 출력부는,상기 버킷에 기록을 수행하는 도중에 오버플로우가 발생하면, 상기 버킷이 다음 순위에 스플릿을 수행하는 차순위 스플릿 버킷인지 여부를 판별하는 스플릿 버킷 판별부; 및상기 판별 결과에 따라 상기 버킷에 기록된 인덱스 작업 레코드 그룹을 상기 버킷에 체인 연결된 오버플로우 버킷 또는 다른 버킷의 스플리팅으로부터 신규 생성된 버킷에 기록하는 쓰기 처리부를 포함하는 것을 특징으로 하는 해시 인덱스 구성 장치
16 16
제 14 항에 있어서,상기 인덱스 작업 레코드 그룹 생성부는,상기 처리 요청이 수신되면 해당 데이터의 처리 형태를 표시하는 작업 타입 데이터를 생성하는 작업 타입 데이터 생성부;상기 데이터 처리 요청이 수신되면 상기 해당 데이터에 대한 인덱스 레코드를 생성하는 인덱스 레코드 생성부;상기 생성된 작업 타입 데이터와 상기 생성된 인덱스 레코드를 결합시켜 인덱스 작업 레코드를 생성하는 인덱스 작업 레코드 생성부; 및생성된 적어도 하나의 인덱스 작업 레코드를 묶어 하나의 인덱스 작업 레코드 그룹으로 하여 상기 인덱스 작업 레코드 그룹들을 상기 쓰기 버퍼에 기록하는 인덱스 작업 레코드 그룹 생성부를 포함하는 것을 특징으로 하는 해시 인덱스 구성 장치
17 17
제 15 항에 있어서,상기 인덱스 작업 레코드 그룹 출력부는 부하율(load factor)이 임계치 이상인지 여부를 판별하는 부하 상태 판별부를 더 포함하는 것을 특징으로 하는 해시 인덱스 구성 장치
18 18
제 17 항에 있어서,상기 스플릿 버킷 판별부에 의해 상기 버킷이 상기 차순위 스플릿 버킷으로 판별되고 상기 부하 상태 판별부에 의해 상기 부하율이 상기 임계치 이상인 것으로 판별되면, 상기 인덱스 작업 레코드 그룹 출력부는,상기 차순위 스플릿 버킷을 검색하는 차순위 스플릿 버킷 검색부;상기 검색된 차순위 스플릿 버킷에 체인 연결된 오버플로우 버킷을 모두 추출하는 오버플로우 버킷 추출부;상기 검색된 차순위 스플릿 버킷과 상기 추출된 오버플로우 버킷에 포함된 모든 인덱스 작업 레코드 그룹으로부터 동일 데이터 처리 요청을 담은 인덱스 작업 레코드를 모두 추출하는 인덱스 작업 레코드 추출부;추출된 인덱스 작업 레코드들과 추출되지 않고 남아있는 인덱스 작업 레코드들을 비교하여 인덱스 레코드의 키 정보가 동일한 것끼리 삭제하는 삭제 작업 처리부; 및삭제되지 않고 남은 인덱스 작업 레코드들을 수집하며, 상기 수집된 인덱스 작업 레코드들을 상기 추출된 오버플로우 버킷 또는 상기 신규 생성된 버킷에 기록하는 쓰기 처리부를 포함하며,상기 스플릿 버킷 판별부가 상기 버킷을 상기 차순위 스플릿 버킷이 아닌 것으로 판별하거나, 상기 스플릿 버킷 판별부에 의해 상기 버킷이 상기 차순위 스플릿 버킷으로 판별되고 상기 부하 상태 판별부에 의해 상기 부하율이 상기 임계치 미만인 것으로 판별되면, 상기 인덱스 작업 레코드 그룹 출력부는,오버플로우 버킷을 생성하는 오버플로우 버킷 생성부;생성된 오버플로우 버킷을 상기 버킷에 체인 연결시키는 체인 연결부; 및상기 버킷에 기록된 인덱스 작업 레코드 그룹을 상기 버킷에 체인 연결된 오버플로우 버킷에 기록하는 쓰기 처리부를 포함하는 것을 특징으로 하는 해시 인덱스 구성 장치
19 19
데이터를 저장하는 데이터 저장 장치로서,주기억장치에서 쓰기 버퍼를 할당하는 쓰기 할당부; 데이터의 처리 요청과 관련된 정보인 인덱스 작업 레코드 그룹들을 할당된 쓰기 버퍼에 기록하는 인덱스 작업 레코드 그룹 생성부; 상기 쓰기 버퍼에 기록된 인덱스 작업 레코드 그룹들 중에서 선택된 적어도 하나의 인덱스 작업 레코드 그룹을 해시 함수에 의해 정해진 보조기억장치의 버킷(bucket)에 기록하는 인덱스 작업 레코드 그룹 출력부; 및 상기 버킷에 기록된 인덱스 작업 레코드 그룹과 관련된 정보를 이용하여 상기 데이터에 대한 해시 인덱스를 구성하는 해시 인덱스 구성부를 포함하는 해시 인덱스 구성 장치를 포함하는 것을 특징으로 하는 데이터 저장 장치
20 20
제 19 항에 있어서,상기 데이터 저장 장치는 SSD(Solid State Drive)인 것을 특징으로 하는 데이터 저장 장치
지정국 정보가 없습니다
패밀리정보가 없습니다
국가 R&D 정보가 없습니다.