[go: up one dir, main page]

KR100907477B1 - 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법 - Google Patents

플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법 Download PDF

Info

Publication number
KR100907477B1
KR100907477B1 KR1020070071155A KR20070071155A KR100907477B1 KR 100907477 B1 KR100907477 B1 KR 100907477B1 KR 1020070071155 A KR1020070071155 A KR 1020070071155A KR 20070071155 A KR20070071155 A KR 20070071155A KR 100907477 B1 KR100907477 B1 KR 100907477B1
Authority
KR
South Korea
Prior art keywords
index
page
flash memory
buffer
entries
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Expired - Fee Related
Application number
KR1020070071155A
Other languages
English (en)
Other versions
KR20090007926A (ko
Inventor
김상욱
장지웅
황규정
Original Assignee
한양대학교 산학협력단
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by 한양대학교 산학협력단 filed Critical 한양대학교 산학협력단
Priority to KR1020070071155A priority Critical patent/KR100907477B1/ko
Publication of KR20090007926A publication Critical patent/KR20090007926A/ko
Application granted granted Critical
Publication of KR100907477B1 publication Critical patent/KR100907477B1/ko
Expired - Fee Related legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Images

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F13/00—Interconnection of, or transfer of information or other signals between, memories, input/output devices or central processing units
    • G06F13/14—Handling requests for interconnection or transfer
    • G06F13/16—Handling requests for interconnection or transfer for access to memory bus
    • G06F13/1668—Details of memory controller
    • G06F13/1673—Details of memory controller using buffers
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F12/00—Accessing, addressing or allocating within memory systems or architectures
    • G06F12/02—Addressing or allocation; Relocation
    • G06F12/0223—User address space allocation, e.g. contiguous or non contiguous base addressing
    • G06F12/0292—User address space allocation, e.g. contiguous or non contiguous base addressing using tables or multilevel address translation means
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F9/00—Arrangements for program control, e.g. control units
    • G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
    • G06F9/46—Multiprogramming arrangements
    • G06F9/50—Allocation of resources, e.g. of the central processing unit [CPU]
    • G06F9/5005—Allocation of resources, e.g. of the central processing unit [CPU] to service a request
    • G06F9/5011—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals
    • G06F9/5016—Allocation of resources, e.g. of the central processing unit [CPU] to service a request the resources being hardware resources other than CPUs, Servers and Terminals the resource being the memory

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Information Retrieval, Db Structures And Fs Structures Therefor (AREA)

Abstract

플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치 및 방법이 개시된다. 갱신지연 버퍼부에는 플래시 메모리에 저장되어 있거나 저장될 연산대상 데이터 및 연산대상 데이터에 대해 수행될 연산의 종류를 포함하는 버퍼 엔트리가 저장된다. 버퍼 엔트리 생성부는 플래시 메모리에 대해 연산대상 데이터를 기록하기 위한 삽입연산 또는 플래시 메모리로부터 연산대상 데이터를 제거하기 위한 삭제연산의 수행이 지시되면 수행될 연산에 대응하는 버퍼 엔트리를 생성한다. 인덱스 관리부는 갱신지연 버퍼부의 저장가능공간이 사전에 설정된 임계값보다 작아지면 플래시 메모리에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하고, 병합대상 페이지에 기록되어 있는 인덱스 엔트리를 독출하여 메인 메모리에 로딩한 후 갱신지연 버퍼부에 저장되어 있는 버퍼 엔트리를 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성한다. 본 발명에 따르면, 플래시 메모리의 쓰기연산과 소거연산의 횟수를 감소시켜 플래시 메모리의 수명이 연장된다.
플래시 메모리, 인덱스, 지연버퍼, 엔트리, 페이지

Description

플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치 및 방법{Apparatus and method for managing index of data stored in flash memory}
도 1은 본 발명에 따른 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치에 대한 바람직한 실시예의 상세한 구성을 도시한 블록도,
도 2는 플래시 메모리에 저장되어 있는 인덱스 페이지의 예를 도시한 도면,
도 3은 갱신지연 버퍼부에 저장된 버퍼 엔트리의 예를 도시한 도면,
도 4는 인덱스 관리부의 상세한 구성을 도시한 블록도,
도 5는 본 발명에 따른 인덱스 정보 관리 장치에서 인덱스 페이지를 생성하기 위한 벌크-로드연산의 수행과정을 도시한 흐름도,
도 6은 본 발명에 따른 인덱스 정보 관리 방법에 대한 바람직한 실시예의 수행과정을 도시한 흐름도,
도 7은 본 발명에 따른 인덱스 정보 관리 장치에서 삽입 또는 삭제연산과정에 대한 일 실시예의 수행과정을 도시한 흐름도,
도 8은 본 발명에 따른 인덱스 정보 관리 장치에서 삽입 또는 삭제연산과정에 대한 다른 실시예의 수행과정을 도시한 흐름도,
도 9는 본 발명에 따른 인덱스 정보 관리 장치에서 삽입 또는 삭제연산과정에 대한 또 다른 실시예의 수행과정을 도시한 흐름도,
도 10a 및 도 10b는 각각 단위병합연산의 수행대상이 되는 플래시 메모리의 데이터 및 갱신지연 버퍼부의 데이터를 도시한 도면,
도 11은 본 발명에 따른 인덱스 정보 관리 방법에 있어서 단위병합연산의 수행과정을 도시한 흐름도,
도 12는 도 11에 도시된 단위병합연산의 페이지 재구성단계의 구체적인 구성을 도시한 흐름도,
도 13은 단위병합연산시 단위병합 가능유닛과 단위병합 가능셋을 메인 메모리 내에서 병합한 결과를 도시한 도면, 그리고,
도 14는 본 발명에 따른 인덱스 정보 관리 방법에 있어서 검색연산의 수행과정을 도시한 흐름도이다.
본 발명은 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치 및 방법에 관한 것으로, 보다 상세하게는 플래시 메모리에 저장된 데이터에 대하여 발생하는 다양한 연산을 효율적으로 처리하는 인덱스 정보를 생성하고 관리하는 장치 및 방법에 관한 것이다.
플래시 메모리는 동일한 크기의 연속적인 블록으로 구성되며, 하나의 블록은 동일한 크기의 연속적인 페이지로 구성된다. 플래시 메모리에서 수행 가능한 연산은 읽기, 쓰기 및 소거의 세가지이다. 읽기 및 쓰기 연산은 페이지 단위로 수행되 며, 소거 연산은 블록 단위로 수행된다. 이때, 쓰기 연산은 읽기 연산에 비해 많은 수행시간이 소요되며, 쓰기 연산에 비해 더 많은 수행시간이 소요되는 소거 연산을 유발시킨다. 따라서 쓰기 연산의 횟수를 줄일수록 플래시 메모리의 전반적인 성능이 향상된다.
이러한 플래시 메모리는 현재 많은 분야에서 주 저장 장치로 사용되고 있으나 다른 저장 장치와는 구별되는 특성이 있다.
플래시 메모리의 첫 번째 특성은 읽기 연산과 쓰기, 소거 연산의 수행 속도에 큰 차이가 있다는 것이다. 플래시 메모리의 읽기 연산과 쓰기 연산은 페이지 단위로 수행되며, 한 페이지에 쓰기 연산을 수행하는 시간은 읽기 연산에 비하여 20배 가량 느리다. 또한 소거 연산은 여러 개의 페이지로 구성된 블록 단위로 수행되는데 그 수행 속도는 읽기 속도와 비교하여 200배 가량 느리다.
플래시 메모리의 두 번째 특성은 소거 연산이 수행된 페이지에만 쓰기 연산을 수행할 수 있다는 것이다. 즉, 플래시 메모리에 저장된 데이터가 갱신되어도 동일한 페이지에 덮어쓰는 것은 불가능하며 새로운 빈 페이지에 기록하여야 한다. 이 때, 갱신할 데이터가 저장되어 있던 페이지 내에 존재하는 다른 모든 유효한 데이터들도 모두 복사해야 하는 부하가 추가적으로 발생한다. 기존의 페이지는 추후에 소거 연산을 통하여 다시 기록 가능한 상태가 된다.
플래시 메모리의 세 번째 특성은 그 수명이 결정되어 있다는 것이다. 플래시 메모리를 구성하는 페이지의 각 블록은 100,000 ~ 1,000,000번의 소거 연산이 이루어지고 나면 더 이상 사용이 불가능하다. 따라서 플래시 페이지에 대한 잦은 덮어 쓰기는 빈 페이지의 급격한 소모를 유발시키고, 이는 빈 페이지를 제공하기 위한 소거 연산을 유발시켜 결과적으로 플래시 메모리의 수명을 단축시킨다.
상술한 바와 같은 플래시 메모리의 특성으로 인하여 기존의 일반적인 저장장치에 적용되는 인덱싱 방법은 플래시 메모리에 적합하지 않다. 종래의 가장 대표적인 인덱스 구조로는 B+트리가 있다. B+트리는 하드 디스크 기반 인덱스에서 성능 감소의 주원인인 디스크의 입출력을 효과적으로 감소시키는 것을 주목적으로 고안되었다. 그 결과 큰 성능 향상을 이루었으며 현재 하드 디스크 기반 데이터베이스 시스템에서 가장 널리 쓰이는 인덱스 구조이다.
플래시 메모리에서 B+트리를 그대로 사용하는 경우, 레코드가 삽입 또는 삭제될 때 플래시 페이지에는 비록 여유 공간이 존재하더라도 동일한 페이지에 덮어쓸 수 없기 때문에 새로운 페이지를 할당하여 해당 노드의 변경된 상태를 저장해야 한다. 이 때 오버플로 또는 언더플로우 현상이 발생하면 해당 노드는 분할 또는 병합이 이루어지고 이는 상위 노드에 영향을 미친다. 즉, 상위 노드에 대응되는 플래시 페이지에서도 새로운 페이지의 할당 및 복사 연산이 이루어져야 한다. B+트리에서는 이러한 분할과 병합이 리프 노드로부터 루트 노드에 이르기까지 연쇄적으로 발생할 수 있다. 이와 같이 데이터의 삽입과 삭제로 잦은 덮어쓰기를 유발시키는 B+트리는 플래시 메모리의 물리적 특성으로 인하여 플래시 메모리의 수명을 단축시키며, 인덱스에서 발생하는 다양한 연산을 수행함에 있어서 하드 디스크에서와 같은 성능을 기대하기 어렵다.
플래시 메모리를 물리적 기반으로 하는 종래의 인덱스 구조로는 B-트리를 플 래시 메모리의 특성에 맞게 개선한 BFTL(B-Tree Flash Translation Layer)이 있다. 플래시 메모리에 대한 B+트리의 구현상의 문제점에서 나타난 바와 같이 플래시 메모리의 특성상 페이지에 여유 공간이 존재하더라도 그 공간을 활용할 수 없다. 따라서 BFTL에서는 인덱스 엔트리들을 플래시 페이지에 기록할 때 B-트리와는 달리 서로 다른 인덱스 노드에 속하는 엔트리라 할지라도 하나의 플래시 페이지에 최대한 가득 채워서 저장한다.
이와 같이 BFTL은 B-트리와는 달리 하나의 플래시 페이지에 서로 다른 인덱스 노드에 속하는 엔트리가 존재하기 때문에 BFTL을 이용하는 어플리케이션에게 B-트리를 이용하는 것과 동일하게 보여주기 위한 추가적인 메커니즘이 필요하다. 먼저 BFTL에서는 동일한 인덱스 노드에 속하는 엔트리들의 물리적 저장 위치를 식별할 수 있는 메커니즘이 필요하다. 이를 위해 BFTL에서는 노드 변환 테이블이라는 자료 구조를 이용한다. 노드 변환 테이블은 동일 노드에 소속된 인덱스 엔트리들이 저장된 주소들의 연결 리스트를 원소로 가지는 집합이다. 노드 변환 테이블은 메인 메모리 내에 상주하며 노드의 수가 증가함에 따라 그 크기가 증가하므로 메인 메모리의 사용량을 증가시킨다. BFTL에서 인덱스의 탐색은 이러한 노드 변환 테이블을 이용하여 메인 메모리 내에서 인덱스 노드를 구축해 가며 수행된다. 이 과정에서 다수의 서로 다른 플래시 페이지들을 액세스해야 하므로 검색 성능은 감소하며, 인덱스 노드를 구축하기 위해 메인 메모리 사용량이 증가한다. 다음으로 BFTL에서 플래시 페이지에 저장된 인덱스 엔트리들은 각기 자신이 소속된 노드를 나타내는 추가 정보를 포함한다. 만약, 인덱스 노드의 분할 또는 합병이 발생하면 이러한 추가 정보로 인하여 다수의 페이지에 분산되어 저장된 인덱스 엔트리들의 갱신이 유발된다. 그 결과, 대상 인덱스 엔트리들을 포함하는 모든 플래시 페이지들은 새로운 페이지로 복사되어야 한다.
상술한 바와 같이 BFTL은 서로 다른 인덱스 노드에 속하는 엔트리들을 하나의 플래시 페이지에 저장함으로써 불필요한 데이터의 복사에 따른 부하를 감소시키며, 플래시 페이지를 가득 채움으로써 기록되는 페이지의 수를 감소시킨다. 그러나 BFTL은 그 구조로 인하여 메인 메모리의 사용량이 증가하고 검색 성능이 감소하게 되며, 인덱스 노드의 분할 또는 합병 시 다수의 플래시 페이지가 복사되는 부하를 유발한다.
본 발명이 이루고자 하는 기술적 과제는 플래시 메모리의 물리적 특성을 고려하여 인덱스의 동적인 삽입과 삭제로 인한 플래시 페이지의 쓰기 연산과 소거 연산의 횟수를 감소시킬 수 있고, 플래시 메모리에 저장된 데이터에 대하여 인덱스 엔트리들을 효과적으로 클러스터링함으로써 빠른 검색을 지원할 수 있으며, 플래시 페이지의 이용률을 높여 저장 공간의 효율성을 보장할 수 있는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치 및 방법을 제공하는 데 있다.
본 발명이 이루고자 하는 다른 기술적 과제는 플래시 메모리의 물리적 특성을 고려하여 인덱스의 동적인 삽입과 삭제로 인한 플래시 페이지의 쓰기 연산과 소거 연산의 횟수를 감소시킬 수 있고, 플래시 메모리에 저장된 데이터에 대하여 인덱스 엔트리들을 효과적으로 클러스터링함으로써 빠른 검색을 지원할 수 있으며, 플래시 페이지의 이용률을 높여 저장 공간의 효율성을 보장할 수 있는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체를 제공하는 데 있다.
상기의 기술적 과제를 달성하기 위한, 본 발명에 따른 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치는, 플래시 메모리에 저장되어 있거나 저장될 연산대상 데이터 및 상기 연산대상 데이터에 대해 수행될 연산의 종류를 포함하는 버퍼 엔트리가 저장되는 갱신지연 버퍼부; 상기 플래시 메모리에 대해 연산대상 데이터를 기록하기 위한 삽입연산 또는 상기 플래시 메모리로부터 연산대상 데이터를 제거하기 위한 삭제연산의 수행이 지시되면 수행될 연산에 대응하는 버퍼 엔트리를 생성하여 상기 갱신지연 버퍼부에 저장하는 버퍼 엔트리 생성부; 및 상기 갱신지연 버퍼부의 저장가능공간이 사전에 설정된 임계값보다 작아지면 상기 갱신지연 버퍼부가 빌 때까지, 상기 플래시 메모리에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하고, 상기 병합대상 페이지에 기록되어 있는 인덱스 엔트리를 독출하여 메인 메모리에 로딩한 후 상기 갱신지연 버퍼부에 저장되어 있는 버퍼 엔트리를 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성하는 인덱스 관리부;를 구비한다.
상기의 다른 기술적 과제를 달성하기 위한, 본 발명에 따른 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법은, (a) 플래시 메모리에 대해 연산대상 데이터를 기록하기 위한 삽입연산 또는 상기 플래시 메모리로부터 연산대상 데이터를 제거하기 위한 삭제연산의 수행이 지시되면 수행될 연산에 대응하여 플래시 메모리에 저장되어 있거나 저장될 연산대상 데이터 및 상기 연산대상 데이터에 대해 수행될 연산의 종류를 포함하는 버퍼 엔트리를 생성하여 갱신지연 버퍼에 저장하는 단계; (b) 상기 갱신지연 버퍼부의 저장가능공간이 사전에 설정된 임계값보다 작아지면 상기 플래시 메모리로부터 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하는 단계; 및 (c) 상기 병합대상 페이지에 기록되어 있는 인덱스 엔트리를 독출하여 메인 메모리에 로딩한 후 상기 갱신지연 버퍼에 저장되어 있는 버퍼 엔트리를 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성하는 단계;를 갖는다.
이에 의해 플래시 메모리의 쓰기 연산과 소거 연산의 횟수를 감소시킴으로써 플래시 메모리의 수명을 연장시킬 수 있으며, 플래시 페이지의 이용률을 높여 저장 공간의 효율성을 보장할 수 있다.
이하에서 첨부된 도면들을 참조하여 본 발명에 따른 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치 및 방법의 바람직한 실시예에 대해 상세하게 설명한다.
도 1은 본 발명에 따른 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치에 대한 바람직한 실시예의 상세한 구성을 도시한 블록도이다.
도 1을 참조하면, 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치(100)는 인덱스 생성부(110), 버퍼 엔트리 생성부(120), 갱신지연 버퍼부(130), 인덱스 관리부(140), 메인 메모리(150) 버퍼관리부(160), 디렉토리 관리부(170) 및 검색부(180)를 구비한다.
인덱스 생성부(110)는 플래시 메모리(190)에 인덱스 페이지가 존재하지 않으면, 플래시 메모리(190)에 저장되어 있는 전체 레코드에 대해 인덱스 엔트리를 생성한 후 사전에 설정되어 있는 기준개수에 해당하는 인덱스 엔트리로 이루어진 인덱스 페이지를 생성하여 플래시 메모리(190)의 빈 페이지에 저장한다. 이와 같이 인덱스 생성부(110)에 의해 플래시 메모리(190)에 저장되어 있는 데이터를 기초로 인덱스 페이지를 구성하는 연산을 벌크-로드 연산이라 한다.
도 2에는 플래시 메모리(190)에 저장되어 있는 인덱스 페이지의 예가 도시되어 있다. 도 2를 참조하면, 플래시 메모리(190)에는 인덱스(210)와 플래시 페이지(240)가 저장된다. 인덱스(210)는 인덱스 페이지의 집합이며, 인덱스 페이지(220)는 인덱스 엔트리들을 저장하는 단위이다. 각각의 인덱스 페이지는 플래시 페이지에 대응되어 저장되며, 인덱스에서 논리적으로 연속적인 인덱스 페이지들이 플래시 메모리(190) 내에서 물리적으로 연속될 필요는 없다. 인덱스 페이지(220)는 다수의 인덱스 엔트리(230)를 포함한다. 인덱스 엔트리(230)는 기본적으로 연산대상 데이터(즉, 레코드의 키값) 및 연산대상 데이터의 위치정보를 포함한다. 각각의 인덱스 페이지는 포함하는 인덱스 엔트리의 수에 따라 빈 공간이 존재할 수 있으며, 인덱스 페이지 내의 인덱스 엔트리들은 레코드의 키값의 크기에 따라 정렬되어 저장된다. 이때 레코드의 키값이란 대응되는 레코드를 식별할 수 있는 필드의 실제 값을 의미하며, 레코드의 위치정보란 플래시 메모리(190)에 저장된 레코드의 주소를 의미한다.
버퍼 엔트리 생성부(120)는 플래시 메모리(190)에 대해 연산대상 데이터를 기록하기 위한 삽입연산 또는 플래시 메모리(190)로부터 연산대상 데이터를 제거하기 위한 삭제연산의 수행이 지시되면 수행될 연산에 대응하는 버퍼 엔트리를 생성한다. 버퍼 엔트리는 기본적으로 플래시 메모리(190)에 저장되어 있거나 저장될 연산대상 데이터(즉, 레코드의 키값), 연산대상 데이터의 위치정보 및 연산대상 데이터에 대해 수행될 연산의 종류를 포함한다. 버퍼 엔트리는 엔트리 저장구조에 따라 갱신지연 버퍼부(130) 내에서 상이한 형태로 유지되거나 추가적인 정보를 포함할 수 있다. 일예로 버퍼 엔트리들은 키값의 순서대로 갱신지연 버퍼부(130)에 저장될 수 있다. 이러한 구조에서는 버퍼 엔트리의 삽입 및 삭제 시에 정렬된 순서를 유지하기 위한 부하가 발생하나 이진탐색을 통해 엔트리에 대한 효율적인 검색을 수행할 수 있는 이점이 있다. 이때 동일한 레코드에 대해 서로 다른 연산이 발생하면 갱신지연 버퍼부(130) 내에는 최신의 연산에 관련된 버퍼 엔트리만 유지된다. 다른 예로 갱신지연 버퍼부(130) 내에 버퍼 엔트리들이 이진탐색트리의 형태로 저장되는 경우에 버퍼 엔트리에는 왼쪽 자식 포인터 및 오른쪽 자식 포인터가 추가적으로 포함된다. 이러한 구조에서는 버퍼 엔트리들을 이진탐색트리의 형태로 유지해야 하는 부하가 존재하나, 갱신지연 버퍼부(130) 내의 엔트리에 대한 삽입, 삭제 그리고 검색을 효율적으로 수행할 수 있는 이점이 있다. 이 경우에도 동일한 레코드에 대해 서는 최신의 연산에 관련된 버퍼 엔트리만 갱신지연 버퍼부(130)에 유지된다.
갱신지연 버퍼부(130)에는 버퍼 엔트리 생성부(120)에 의해 생성된 버퍼 엔트리가 저장된다. 갱신지연 버퍼부(130)는 메인 메모리(150) 내에서 고정된 크기로 유지되거나 별도의 저장수단으로 구성되며, 동적으로 삽입 또는 삭제되는 인덱스 엔트리를 임시로 저장하고 관리하기 위한 장치이다. 도 3에는 갱신지연 버퍼부(130)에 저장된 버퍼 엔트리(310, 320, 330, 340, 350)의 예가 도시되어 있다.
인덱스 관리부(140)는 갱신지연 버퍼부(130)의 저장가능공간이 사전에 설정된 임계값(예를 들면, 저장가능공간의 10%, 0% 등)보다 작아지면 갱신지연 버퍼부(130)가 빌 때까지, 플래시 메모리(190)에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수(예를 들면, 2개)의 인덱스 페이지를 병합대상 페이지로 선정한다. 또한 인덱스 관리부(140)는 선정된 병합대상 페이지에 기록되어 있는 인덱스 엔트리를 독출하여 메인 메모리(150)에 로딩한 후 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리를 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리(190)에 기록될 인덱스 페이지를 구성한다.
도 4는 인덱스 관리부(140)의 상세한 구성을 도시한 블록도이다.
도 4를 참조하면, 인덱스 관리부(140)는 페이지 선정부(410), 엔트리 선정부(420), 페이지 구성부(430), 전처리부(440), 식별정보 할당부(450) 및 엔트리 배분부(460)로 구성된다.
페이지 선정부(410)는 갱신지연 버퍼부(130)의 저장가능공간이 사전에 설정 된 임계값보다 작아지면 플래시 메모리(190)에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수(예를 들면, 2개)의 인덱스 페이지를 병합대상 페이지로 선정한다.
엔트리 선정부(420)는 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리들 중에서 병합대상 페이지들로부터 파악된 기록가능공간에 해당하는 개수의 버퍼 엔트리를 병합가능 엔트리로 선정한다.
페이지 구성부(430)는 병합가능 엔트리를 연산대상 데이터의 크기를 기준으로 메인 메모리(150)에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 임시 인덱스 페이지를 구성한다. 이때 버퍼 엔트리들이 연산의 발생순서대로 갱신지연 버퍼부(130)에 저장되는 구조를 가지고 있으면, 임시 인덱스 페이지를 구성하기 전에 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리들에 대한 전처리과정이 필요하다.
전처리부(440)는 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리들을 연산대상 데이터의 크기를 기준으로 정렬하고, 동일한 연산대상 데이터에 대해 상이한 연산종류가 설정되어 있으면 동일한 연산대상 데이터 중에서 시간적으로 늦게 갱신지연 버퍼부(130)에 저장된 연산대상 데이터 및 그에 대응하는 연산종류에 해당하는 버퍼 엔트리를 제외하고 나머지 연산대상 데이터 및 연산종류에 해당하는 버퍼 엔트리를 제거한다. 이와 같은 전처리부(440)의 동작에 의해 갱신지연 버퍼부(140) 내에서 동일한 키값에 대해 반복적으로 삽입과 삭제연산이 발생한 경우에 이를 통합하여 최신의 정보에 대한 병합연산이 가능하다.
식별정보 할당부(450)는 임시 인덱스 페이지 중에서 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행된 임시 인덱스 페이지에 대해 제1페이지 식별정보를 할당하고, 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행되지 않은 임시 인덱스 페이지에 대해 제2페이지 식별정보를 할당하고, 나머지 임시 임덱스 페이지에 대해 제1페이지 식별정보를 할당한다. 이와 같이 임시 인덱스 페이지를 구분하는 이유는 인덱스의 구성 및 저장시에 플래시 페이지의 이용율이 50% 이상을 만족하는 조건에서 최소한의 쓰기 연산이 수행되도록 하기 위함이다.
엔트리 배분부(460)는 제1페이지 식별정보가 할당된 임시 인덱스 페이지 중에서 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지의 이전 또는 이후에 위치하는 제2페이지 식별정보가 할당된 임시 인덱스 페이지에 제1페이지 식별정보를 다시 할당한 후 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지를 구성하는 엔트리들을 상기 제1페이지 식별정보가 할당된 임시 인덱스 페이지에 배분하여 플래시 메모리(190)에 기록될 인덱스 페이지를 구성한다.
메인 메모리(150)에는 병합연산을 수행하기 위한 플래시 메모리(190)로부터 독출한 인덱스 페이지가 저장된다. 또한 메인 메모리(150)에는 병합연산의 수행시 갱신지연 버퍼부(130)로부터 선정된 병합가능 엔트리가 저장된다. 나아가 메인 메모리(150)에는 본 발명에 따른 인덱스 정보 관리 장치(100)가 인덱스를 생성하거나 갱신하는 과정에서 발생한 중간 데이터가 저장된다. 한편 갱신지연 버퍼부(130)는 메인 메모리(150)로부터 고정적으로 할당받아 구성될 수 있다.
버퍼관리부(160)는 삽입 또는 삭제연산에 대한 수행이 지시되면 갱신지연 버퍼부(130)에 연산대상 데이터에 해당하여 생성된 버퍼 엔트리를 기록한다. 이러한 버퍼관리부(160)의 갱신지연 버퍼부(130)의 관리동작은 버퍼 엔트리의 구조에 따라 상이하다. 일예로 버퍼 엔트리가 이진탐색에 적합한 형태로 관리되는 경우에 있어서, 버퍼관리부(160)는 갱신지연 버퍼부(130)에 버퍼 엔트리 생성부(120)에 의해 생성된 버퍼 엔트리와 동일한 연산대상 데이터를 포함하는 버퍼 엔트리가 존재하면 갱신지연 버퍼부(130)에 기존재하는 버퍼 엔트리의 연산종류를 새롭게 생성된 버퍼 엔트리의 연산종류로 변경한다.
디렉토리 관리부(170)는 플래시 메모리(190)에 저장되어 있는 인덱스 페이지에 논리적 순서에 따라 직접 접근이 가능하도록 하기 위한 디렉토리를 생성한다. 생성된 디렉토리는 파일 시스템이 존재하는 경우에는 파일맵의 형태로 파일 시스템이 유지 및 관리한다. 이때 파일맵은 효율적인 검색을 위해 중간에 삽입 및 삭제가 가능하여야 한다. 이와 달리 파일 시스템이 존재하지 않으면 디렉토리는 파일 시스템에서 제공하는 파일맵과 동일한 형태로 구현된다.
검색부(180)는 검색연산의 요청시 최신의 정보를 저장하고 있는 갱신지연 버퍼부(130)를 우선 검색하여 검색결과를 제공한다. 이때 갱신지연 버퍼부(130)에 검색요청된 값이 존재하지 않으면, 검색부(180)는 디렉토리를 검사하여 검색연산을 수행할 인덱스 페이지를 파악한 후 해당 인덱스 페이지 내에서 이진 탐색을 수행하여 검색요청된 값을 검색하여 검색결과를 제공한다.
도 5는 본 발명에 따른 인덱스 정보 관리 장치에서 인덱스 페이지를 생성하 기 위한 벌크-로드연산의 수행과정을 도시한 흐름도이다.
도 5를 참조하면, 인덱스 생성부(110)는 플래시 메모리(190)에 인덱스 페이지가 존재하는지 여부를 확인한다(S500). 만약 인덱스 페이지가 존재하지 않으면, 인덱스 생성부(110)는 플래시 메모리(190)에 저장되어 있는 전체 레코드를 읽어 인덱스 페이지를 구성할 인덱스 엔트리를 생성한다(S510). 다음으로 인덱스 생성부(110)는 외부로부터 입력받거나 기설정되어 있는 페이지 채움 인수(즉, 하나의 인덱스 페이지에 들어갈 수 있는 인덱스 엔트리의 수)에 해당하는 인덱스 엔트리로 이루어진 인덱스 페이지를 생성한다(S520). 다음으로 인덱스 생성부(110)는 플래시 메모리(190)로부터 플래시 페이지를 할당받아 생성한 인덱스 페이지를 저장한다(S530). 다음으로 디렉토리 관리부(170)는 플래시 메모리(190)에 저장된 인덱스 페이지에 대한 인덱싱 정보를 디렉토리에 반영한다(S540). 마지막으로 인덱스 생성부(110)는 인덱스 페이지를 구성할 인덱스 엔트리가 존재하는지 확인하고(S550), 인덱스 엔트리가 존재하지 않으면 벌크-로드연산을 종료한다.
도 6은 본 발명에 따른 인덱스 정보 관리 방법에 대한 바람직한 실시예의 수행과정을 도시한 흐름도이다.
도 6을 참조하면, 버퍼관리부(160)는 레코드에 대한 삽입 또는 삭제연산의 수행이 지시되면(S600), 지시된 연산에 해당하는 레코드의 키값 및 연산종류를 포함하는 버퍼 엔트리를 갱신지연 버퍼부(130)에 기록한다(S610). 다음으로 인덱스 관리부(140)는 갱신지연 버퍼부(130)의 여유용량이 사전에 설정된 기준값보다 작은지를 확인한다(S620). 만약 여유용량이 사전에 설정된 기준값보다 작으면, 인덱스 관리부(140)는 플래시 메모리(190)로부터 사전에 설정된 개수의 인덱스 페이지로부터 인덱스 엔트리를 독출하여 메인 메모리(150)에 로딩한다(S630). 다음으로 인덱스 관리부(140)는 메인 메모리(150)에 로딩된 인덱스 엔트리와 갱신지연 버퍼부(130)로부터 선정된 개수의 병합가능 엔트리를 병합하여 인덱스 페이지를 재구성한다(S640). 다음으로 인덱스 관리부(140)는 갱신지연 버퍼부(130)에 버퍼 엔트리가 존재하는지 확인한다(S650). 만약 버퍼 엔트리가 존재하면, 인덱스 관리부(140)는 S630단계부터 S640단계를 수행한다. 이와 달리 버퍼 엔트리가 존재하지 않으면, 디렉토리 관리부(170)는 재구성된 인덱스 페이지의 인덱스 정보를 디렉토리에 반영한다(S660).
도 7은 본 발명에 따른 인덱스 정보 관리 장치에서 삽입 또는 삭제연산과정에 대한 일 실시예의 수행과정을 도시한 흐름도이다. 도 7에 도시된 실시예는 연산의 발생시점에 따라 갱신지연 버퍼부(130)의 빈 공간에 버퍼 엔트리가 순차적으로 저장되는 경우에 해당한다.
도 7을 참조하면, 레코드에 대한 삽입 또는 삭제연산의 수행이 지시되면, 버퍼관리부(160)는 갱신지연 버퍼부(130)의 첫번째 빈 공간을 검색한다(S700). 다음으로 버퍼관리부(160)는 검색된 빈 공간에 새로운 버퍼 엔트리를 삽입한다(S710). 다음으로 인덱스 관리부(140)는 갱신지연 버퍼부(130)에 여유공간이 존재하는지 확인한다(S720). 만약 여유공간이 존재하지 않으면, 인덱스 관리부(140)는 병합연산을 수행한다(S730). 도 7을 참조하여 설명한 실시예는 인덱스 엔트리의 삽입과 삭제 시에 효과적이지만, 갱신지연 버퍼부(130) 내에서의 검색 시간은 느린 단점이 있다.
도 8은 본 발명에 따른 인덱스 정보 관리 장치에서 삽입 또는 삭제연산과정에 대한 다른 실시예의 수행과정을 도시한 흐름도이다. 도 8에 도시된 실시예는 버퍼 엔트리를 갱신지연 버퍼부(130)에 키값의 크기에 따라 저장하는 경우에 해당한다.
도 8을 참조하면, 레코드에 대한 삽입 또는 삭제연산의 수행이 지시되면, 버퍼관리부(160)는 갱신지연 버퍼부(130)에 대한 이진탐색을 통해 새로운 버퍼 엔트리와 동일한 키값을 갖는 버퍼 엔트리를 검색한다(S800). 다음으로 버퍼관리부(160)는 동일한 키값의 버퍼 엔트리가 존재하면(S810), 기존의 버퍼 엔트리를 삭제한다(S820). 다음으로 버퍼관리부(130)는 새로운 엔트리를 갱신지연 버퍼부(130)에 저장하고 갱신지연 버퍼부(130)의 엔트리들을 키값을 기준으로 정렬한다(S830). 다음으로 인덱스 관리부(140)는 갱신지연 버퍼부(130)에 여유공간이 존재하는지 확인한다(S840). 만약 여유공간이 존재하지 않으면, 인덱스 관리부(140)는 병합연산을 수행한다(S850). 도 8에 도시된 실시예는 버퍼 엔트리의 삽입과 삭제 시에 정렬된 순서를 유지하는 부하가 존재한다. 그러나 동일 레코드에 대한 서로 다른 연산이 발생하면 최신의 연산만을 유지하므로, 이진탐색을 통하여 갱신지연 버퍼부(130)에 대한 검색을 효율적으로 수행할 수 있다.
도 9는 본 발명에 따른 인덱스 정보 관리 장치에서 삽입 또는 삭제연산과정에 대한 또 다른 실시예의 수행과정을 도시한 흐름도이다. 도 9에 도시된 실시예는 버퍼 엔트리를 갱신지연 버퍼부(130)에 이진탐색트리의 형태로 저장하는 경우에 해 당한다.
도 9를 참조하면, 레코드에 대한 삽입 또는 삭제연산의 수행이 지시되면, 버퍼관리부(160)는 갱신지연 버퍼부(130)에 대한 이진탐색을 통해 새로운 버퍼 엔트리와 동일한 키값을 갖는 버퍼 엔트리를 검색한다(S900). 다음으로 버퍼관리부(160)는 동일한 키값의 버퍼 엔트리가 존재하면(S910), 기존의 버퍼 엔트리를 삭제한다(S920). 다음으로 버퍼관리부(130)는 새로운 엔트리를 갱신지연 버퍼부(130)에 저장하고 갱신지연 버퍼부(130)의 엔트리들이 이진탐색트리구조를 유지하도록 엔트리들의 정보를 갱신한다(S930). 다음으로 인덱스 관리부(140)는 갱신지연 버퍼부(130)에 여유공간이 존재하는지 확인한다(S940). 만약 여유공간이 존재하지 않으면, 인덱스 관리부(140)는 병합연산을 수행한다(S950). 도 9에 도시된 실시예는 동일 레코드에 대한 서로 다른 연산이 발생하면 최신의 연산만을 유지하므로, 버퍼 엔트리의 삽입, 삭제 및 검색을 모두 효율적으로 수행할 수 있으나, 이진탐색트리를 유지하는 부하가 존재한다.
도 7 내지 도 9를 참조하여 설명한 바와 같은 삽입연산 또는 삭제연산을 통해 지속적으로 갱신지연 버퍼부(130)에 버퍼 엔트리가 저장되면 갱신지연 버퍼부(130)의 여유용량이 사전에 설정된 임계값보다 작아지게 된다. 이 경우 인덱스 관리부(140)는 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리를 플래시 메모리(190)에 저장되어 있는 인덱스 페이지의 인덱스 엔트리들과 병합하여 인덱스 페이지를 재구성하는 병합연산을 수행한다. 이때 병합연산은 일정한 개수의 인덱스 페이지에 대해 수행되는 단위병합연산이 복수회 수행되는 형태로 이루어지며, 갱신 지연 버퍼부(130)가 빌 때까지 수행된다.
도 10a 및 도 10b에는 각각 단위병합연산의 수행대상이 되는 플래시 메모리(190)의 데이터 및 갱신지연 버퍼부(130)의 데이터가 도시되어 있다.
도 10a 및 도 10b를 참조하면, 단위병합 가능유닛(1000)은 사전에 설정된 개수의 인덱스 페이지(1010, 1020)로 이루어진 집합이다. 이때 단위병합연산시 단위병합 가능유닛(1000) 내에 저장되어야할 키값의 범위는 단위병합 가능범위로 정의된다. 단위병합연산이 i번째 인덱스 페이지부터 k개의 인덱스 페이지를 대상으로 수행된다면 단위병합 가능범위는 i번째 인덱스 페이지의 최소값부터 (i + k + 1)번째 인덱스 페이지의 최소값 사이가 된다. 0번째 인덱스 페이지는 인덱스 페이지에서 점유할 수 없는 범위에 해당하는 무한소부터 첫 번째 인덱스 페이지의 최소값 사이에 존재하는 인덱스 엔트리들에 대하여 단위병합연산을 수행하기 위해 존재하는 가상의 인덱스 페이지를 의미한다. 도 10a에 도시된 예에서는 단위병합 가능유닛의 단위병합 가능범위는 11보다 크거나 같으며 51보다 작은 수이다. 인덱스 페이지(1010)는 인덱스 엔트리가 기록된 점유영역(1012)과 엔덱스 엔트리가 기록되지 않은 비점유영역(1014)으로 구분된다. 한편 갱신지연 버퍼부(130)의 버퍼 엔트리 중에서 단위병합 가능범위에 포함되는 인덱스 페이지들의 비점유영역에 해당하는 개수의 버퍼 엔트리로 구성되는 집합이 단위병합 가능셋(1030)이다. 도 10b에 도시된 예에서 단위병합 가능셋을 이루는 버퍼 엔트리들은 (12, 삽입), (15, 삭제), (41, 삽입) 및 (42, 삽입)이다.
도 11은 본 발명에 따른 인덱스 정보 관리 방법에 있어서 단위병합연산의 수 행과정을 도시한 흐름도이다.
도 11을 참조하면, 페이지 선정부(410)는 갱신지연 버퍼부(130)의 저장가능공간이 사전에 설정된 임계값보다 작아지면 플래시 메모리(190)에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수(예를 들면, 2개)의 인덱스 페이지를 병합대상 페이지로 선정하고, 병합대상 페이지의 인덱스 엔트리를 메인 메모리(150)에 로딩한다(S1100). 다음으로 엔트리 선정부(420)는 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리들 중에서 병합대상 페이지들로부터 파악된 비점유영역에 해당하는 개수의 버퍼 엔트리를 병합가능 엔트리로 선정한다(S1110). 다음으로 페이지 구성부(430)는 병합가능 엔트리를 키값의 크기를 기준으로 메인 메모리(150)에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 인덱스 페이지를 재구성한다(S1120). 이때 버퍼 엔트리들이 연산의 발생순서대로 갱신지연 버퍼부(130)에 저장되는 구조를 가지고 있으면, 임시 인덱스 페이지를 구성하기 전에 갱신지연 버퍼부(130)에 저장되어 있는 버퍼 엔트리들에 대한 전처리과정이 필요하다.
도 12는 도 11에 도시된 단위병합연산의 페이지 재구성단계의 구체적인 구성을 도시한 흐름도이다.
도 12를 참조하면, 먼저 페이지 구성부(430)는 병합가능 엔트리를 키값의 크기를 기준으로 메인 메모리(150)에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 임시 인덱스 페이지를 구성한다(S1200). 다음으로 식별정보 할당부(450)는 임시 인덱스 페이지 중에서 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행된 임시 인덱스 페이지에 대해 제1페이지 식별정보를 할당하고, 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행되지 않은 임시 인덱스 페이지에 대해 제2페이지 식별정보를 할당한다(S1210).
여기에서 제1페이지 식별정보가 부여된 인덱스 페이지는 단위병합 가능유닛의 점유영역에 속하는 버퍼 엔트리가 존재하는 인덱스 페이지를 의미한다. 즉, 제1페이지 식별정보가 부여된 페이지는 병합 연산의 결과로 반드시 덮어쓰기가 수행되어야 하는 인덱스 페이지를 의미한다. 도 10a에 도시된 실시예의 경우에 단위병합 가능유닛(1000) 중 왼쪽 인덱스 페이지(1010)가 이러한 페이지에 해당한다. 또한 제2페이지 식별정보가 부여된 인덱스 페이지는 단위병합 가능유닛 중 점유영역에 속하는 버퍼 엔트리가 존재하지 않는 인덱스 페이지를 의미한다. 즉, 제2페이지 식별정보가 부여된 페이지는 병합연산으로 인하여 덮어쓰기가 수행될 수도 있고 그렇지 않을 수도 있는 인덱스 페이지를 의미한다. 도 10a에 도시된 실시예의 경우에 단위병합 가능유닛(1000) 중 오른쪽 인덱스 페이지(1020)가 이러한 페이지에 해당한다.
다음으로 엔트리 배분부(460)는 제1페이지 식별정보가 할당된 임시 인덱스 페이지의 인덱스 엔트리 수를 검사한다(S1220). 만약 제1페이지 식별정보가 할당된 임시 인덱스 페이지의 인덱스 엔트리 수가 인덱스 페이지에 대해 설정된 저장가능 엔트리 수(즉, 페이지 채움 인수)의 절반 이하인 임시 인덱스 페이지가 존재하면(S1230), 엔트리 배분부(460)는 해당 임시 인덱스 페이지에 인접한 제2페이지 식별정보가 할당된 임시 인덱스 페이지의 식별정보를 제1페이지 식별정보로 변경한 다(S1240). S1220단계 내지 S1240단계는 제1페이지 식별정보가 부여된 모든 임시 인덱스 페이지에 대해 반복적으로 수행된다.
다음으로 엔트리 배분부(460)는 제2페이지 식별정보가 부여된 임시 인덱스 페이지 중에서 페이지 쓰기 횟수를 감소시킬 수 있는 페이지가 존재하는지 확인한다(S1250). 만약 그러한 임시 인덱스 페이지가 존재하면 해당 페이지의 식별정보를 제1페이지 식별정보로 변경한다(S1260). 다음으로 엔트리 배분부(460)는 제1페이지 식별정보가 부여된 임시 인덱스 페이지에 갱신지연 버퍼부(130)로부터 선정된 병합가능 엔트리들을 균등하게 배분하여 플래시 메모리(190)에 저장할 인덱스 페이지를 재구성한다(S1270). 마지막으로 엔트리 배분부(460)는 재구성된 인덱스 페이지를 플래시 메모리(190)에 저장한다(S1280).
도 13은 단위병합연산시 단위병합 가능유닛과 단위병합 가능셋을 메인 메모리(150) 내에서 병합한 결과를 도시한 도면이다.
도 13을 참조하면, 해당 인덱스 엔트리들을 플래시 페이지에 배분함에 있어제1페이지 식별정보가 부여된 임시 인덱스 페이지(1310, 1330) 중에서 두 번째 나타나는 임시 인덱스 페이지(1330)의 인덱스 엔트리들은 그 수가 하나의 인덱스 페이지에서 저장할 수 있는 총 인덱스 엔트리 수의 절반에 미치지 못한다. 그러므로 해당 인덱스 엔트리들 이전에 존재하는 임시 인덱스 페이지 중에서 제2페이지 식별정보가 부여된 임시 인덱스 페이지(1320)의 식별정보를 제1페이지 식별정보로 변경한다. 다음으로 더 이상 제2페이지 식별정보가 부여된 임시 인덱스 페이지가 존재하지 않으므로 도 8개의 인덱스 엔트리들을 2개의 플래시 페이지(1340, 1350)에 균 등하게 분배한다.
도 11 내지 도 13을 참조하여 설명한 방법에 의해 삽입 및 삭제 연산을 수행하면 인덱스 페이지의 이용률이 50% 이상 보장되면서 쓰기 연산의 횟수를 크게 감소시킬 수 있다. 다만 예외적으로 삭제 연산이 많은 경우 이용률이 50% 이하인 페이지가 생성될 수 있으나, 쓰기 연산의 횟수를 감소시키기 위해 이러한 페이지의 존재를 허용할 수 있다. 또한 성능 향상을 위해 단위 병합 가능 유닛의 크기가 1로 주어진 경우 0번째 노드에 대한 병합 연산은 첫 번째 인덱스 페이지의 병합 연산 시에 같이 수행할 수 있다.
본 발명에서는 삽입 및 삭제 연산을 즉시 인덱스에 반영하지 않고 갱신 지연 버퍼를 이용하므로 검색연산의 과정이 다음과 같이 수정된다. 즉 인덱스에서 검색연산은 먼저 최신의 정보를 저장하고 있는 갱신지연 버퍼부(130)에 대해 수행된다. 만약 요청하는 값이 갱신지연 버퍼부(130)에 존재하지 않으면, 디렉터리를 통하여 인덱스 페이지를 검색한다.
도 14는 본 발명에 따른 인덱스 정보 관리 방법에 있어서 검색연산의 수행과정을 도시한 흐름도이다.
도 14를 참조하면, 검색 연산이 발생하면 검색부(180)는 최신의 정보를 저장하고 있는 갱신지연 버퍼부(130)를 우선 검색한다(1400). 이때 버퍼 엔트리가 생성된 시간순으로 저장되어 있는 구조에서는 검색부(180)는 갱신지연 버퍼부(130)의 후방으로부터 순차 탐색을 실시한다. 이와 달리 버퍼 엔트리가 키값의 크기순서로 저장되어 있거나 이진탐색트리구조로 저장되어 있는 구조에서는 검색부(180)는 갱 신지연 버퍼부(130)에 대해 이진 탐색을 수행한다. 다음으로 검색부(180)는 갱신지연 버퍼부(130) 내에 검색요청된 값이 존재하는지 확인한다(S1410). 만약 갱신지연 버퍼부(130)에 검색요청된 값이 존재하면, 검색부는 해당 값의 주소를 반환한다(S1420). 이와 달리 갱신지연 버퍼부(130)에 검색요청된 값이 존재하지 않으면, 검색부(180)는 디렉토리를 검사하여 검색연산을 수행할 인덱스 페이지를 찾는다(1430). 다음으로 검색부(180)는 인덱스 페이지 내에서 이진 탐색을 수행하여 검색요청된 값을 검색한다(1440). 만약 인덱스 페이지 내에 검색요청된 값이 존재하면, 검색부(180)는 해당 값의 주소를 반환한다(1450). 이와 달리 인덱스 페이지 내에 검색요청된 값이 존재하지 않으면, 검색부(180)는 오류를 반환한다(1460).
본 발명은 또한 컴퓨터로 읽을 수 있는 기록매체에 컴퓨터가 읽을 수 있는 코드로서 구현하는 것이 가능하다. 컴퓨터가 읽을 수 있는 기록매체는 컴퓨터 시스템에 의하여 읽혀질 수 있는 데이터가 저장되는 모든 종류의 기록장치를 포함한다. 컴퓨터가 읽을 수 있는 기록매체의 예로는 ROM, RAM, CD-ROM, 자기 테이프, 플로피디스크, 광데이터 저장장치 등이 있으며, 또한 캐리어 웨이브(예를 들어 인터넷을 통한 전송)의 형태로 구현되는 것도 포함한다. 또한 컴퓨터가 읽을 수 있는 기록매체는 네트워크로 연결된 컴퓨터 시스템에 분산되어 분산방식으로 컴퓨터가 읽을 수 있는 코드가 저장되고 실행될 수 있다.
이상에서 본 발명의 바람직한 실시예에 대해 도시하고 설명하였으나, 본 발명은 상술한 특정의 바람직한 실시예에 한정되지 아니하며, 청구범위에서 청구하는 본 발명의 요지를 벗어남이 없이 당해 발명이 속하는 기술분야에서 통상의 지식을 가진 자라면 누구든지 다양한 변형 실시가 가능한 것은 물론이고, 그와 같은 변경은 청구범위 기재의 범위 내에 있게 된다.
본 발명에 따른 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치 및 방법에 의하면, 인덱스 엔트리들을 효과적으로 클러스터링 함으로써 플래시 페이지의 이용률을 높이면서 효율적인 검색이 가능하다. 또한 플래시 메모리의 물리적 특성을 반영하여 동적인 삽입과 삭제를 지연시킴으로써, 플래시 메모리의 쓰기 연산과 소거 연산의 횟수를 감소시켜 플래시 메모리의 수명을 연장시킬 수 있다. 나아가 적은 메모리를 이용하며 저전력으로 동작하기 때문에 모바일 또는 내장형 시스템에서 적용될 수 있다.

Claims (15)

  1. 플래시 메모리에 저장되어 있거나 저장될 연산대상 데이터 및 상기 연산대상 데이터에 대해 수행될 연산의 종류를 포함하는 버퍼 엔트리가 저장되는 갱신지연 버퍼부;
    상기 플래시 메모리에 대해 연산대상 데이터를 기록하기 위한 삽입연산 또는 상기 플래시 메모리로부터 연산대상 데이터를 제거하기 위한 삭제연산의 수행이 지시되면 수행될 연산에 대응하는 버퍼 엔트리를 생성하여 상기 갱신지연 버퍼부에 저장하는 버퍼 엔트리 생성부; 및
    상기 갱신지연 버퍼부의 저장가능공간이 사전에 설정된 임계값보다 작아지면 상기 갱신지연 버퍼부가 빌 때까지, 상기 플래시 메모리에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하고, 상기 병합대상 페이지에 기록되어 있는 인덱스 엔트리를 독출하여 메인 메모리에 로딩한 후 상기 갱신지연 버퍼부에 저장되어 있는 버퍼 엔트리를 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성하는 인덱스 관리부;를 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치.
  2. 제 1항에 있어서,
    플래시 메모리에 인덱스 페이지가 존재하지 않으면, 플래시 메모리에 저장되어 있는 전체 레코드에 대해 상기 인덱스 엔트리를 생성한 후 사전에 설정되어 있는 기준개수에 해당하는 인덱스 엔트리로 이루어진 인덱스 페이지를 생성하여 플래시 메모리의 빈 페이지에 저장하는 인덱스 생성부를 더 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치.
  3. 제 1항에 있어서,
    상기 갱신지연 버퍼부에 저장되어 있는 버퍼 엔트리들을 연산대상 데이터의 키값의 크기를 기준으로 정렬하고, 동일한 연산대상 데이터에 대해 상이한 연산종류가 설정되어 있으면 동일한 연산대상 데이터 중에서 시간적으로 늦게 상기 갱신지연 버퍼부에 저장된 연산대상 데이터 및 그에 대응하는 연산종류에 해당하는 버퍼 엔트리를 제외하고 나머지 연산대상 데이터 및 연산종류에 해당하는 버퍼 엔트리를 제거하는 전처리부를 더 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치.
  4. 제 1항에 있어서,
    상기 갱신지연 버퍼부에 상기 생성된 버퍼 엔트리와 동일한 연산대상 데이터를 포함하는 버퍼 엔트리가 존재하면 상기 갱신지연 버퍼부에 기존재하는 버퍼 엔트리의 연산종류를 상기 생성된 버퍼 엔트리의 연산종류로 변경하는 버퍼 관리부를 더 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관 리 장치.
  5. 제 1항, 제 3항 또는 제 4항 중 어느 한 항에 있어서,
    상기 인덱스 관리부는 상기 갱신지연 버퍼부에 저장되어 있는 버퍼 엔트리들 중에서 상기 병합대상 페이지들로부터 파악된 기록가능공간에 해당하는 개수의 버퍼 엔트리를 병합가능 엔트리로 선정하고, 상기 병합가능 엔트리를 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치.
  6. 제 1항, 제 3항 또는 제 4항 중 어느 한 항에 있어서,
    상기 인덱스 관리부는,
    상기 갱신지연 버퍼부의 저장가능공간이 사전에 설정된 임계값보다 작아지면 상기 플래시 메모리에 저장되어 있는 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 인덱스 페이지 중에서 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하는 페이지 선정부;
    상기 갱신지연 버퍼부에 저장되어 있는 버퍼 엔트리들 중에서 상기 병합대상 페이지들로부터 파악된 기록가능공간에 해당하는 개수의 버퍼 엔트리를 병합가능 엔트리로 선정하는 엔트리 선정부;
    상기 병합가능 엔트리를 연산대상 데이터의 키값의 크기를 기준으로 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 임시 인덱스 페이지를 구성하는 페이지 구성부;
    상기 임시 인덱스 페이지 중에서 상기 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행된 임시 인덱스 페이지에 대해 제1페이지 식별정보를 할당하고, 상기 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행되지 않은 임시 인덱스 페이지에 대해 제2페이지 식별정보를 할당하고, 나머지 임시 임덱스 페이지에 대해 제1페이지 식별정보를 할당하는 식별정보 할당부; 및
    상기 제1페이지 식별정보가 할당된 임시 인덱스 페이지 중에서 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지의 이전 또는 이후에 위치하는 제2페이지 식별정보가 할당된 임시 인덱스 페이지에 제1페이지 식별정보를 다시 할당한 후 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지를 구성하는 엔트리들을 상기 제1페이지 식별정보가 할당된 임시 인덱스 페이지에 배분하여 상기 플래시 메모리에 기록될 인덱스 페이지를 구성하는 엔트리 배분부;를 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치.
  7. 제 6항에 있어서,
    상기 엔트리 배분부는 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지의 이전 또는 이후에 위치하는 제2페이지 식별정보가 할당된 임시 인덱스 페이지 중에서 페이지 이용율이 높은 페이지에 제1페이지 식별정보를 다시 할당하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치.
  8. (a) 플래시 메모리에 대해 연산대상 데이터를 기록하기 위한 삽입연산 또는 상기 플래시 메모리로부터 연산대상 데이터를 제거하기 위한 삭제연산의 수행이 지시되면 수행될 연산에 대응하여 플래시 메모리에 저장되어 있거나 저장될 연산대상 데이터 및 상기 연산대상 데이터에 대해 수행될 연산의 종류를 포함하는 버퍼 엔트리를 생성하여 갱신지연 버퍼에 저장하는 단계;
    (b) 상기 갱신지연 버퍼부의 저장가능공간이 사전에 설정된 임계값보다 작아지면 상기 플래시 메모리로부터 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하는 단계; 및
    (c) 상기 병합대상 페이지에 기록되어 있는 인덱스 엔트리를 독출하여 메인 메모리에 로딩한 후 상기 갱신지연 버퍼에 저장되어 있는 버퍼 엔트리를 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성하는 단계;를 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  9. 제 8항에 있어서,
    (d) 플래시 메모리에 인덱스 페이지가 존재하지 않으면, 플래시 메모리에 저 장되어 있는 전체 레코드에 대해 상기 인덱스 엔트리를 생성한 후 사전에 설정되어 있는 기준개수에 해당하는 인덱스 엔트리로 이루어진 인덱스 페이지를 생성하여 플래시 메모리의 빈 페이지에 저장하는 단계를 더 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  10. 제 8항에 있어서,
    (e) 상기 갱신지연 버퍼에 저장되어 있는 버퍼 엔트리들을 연산대상 데이터의 키값의 크기를 기준으로 정렬하고, 동일한 연산대상 데이터에 대해 상이한 연산종류가 설정되어 있으면 동일한 연산대상 데이터 중에서 시간적으로 늦게 상기 갱신지연 버퍼에 저장된 연산대상 데이터 및 그에 대응하는 연산종류에 해당하는 버퍼 엔트리를 제외하고 나머지 연산대상 데이터 및 연산종류에 해당하는 버퍼 엔트리를 제거하는 단계를 더 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  11. 제 8항에 있어서,
    (f) 상기 갱신지연 버퍼에 상기 생성된 버퍼 엔트리와 동일한 연산대상 데이터를 포함하는 버퍼 엔트리가 존재하면 상기 갱신지연 버퍼에 기존재하는 버퍼 엔트리의 연산종류를 상기 생성된 버퍼 엔트리의 연산종류로 변경하는 단계를 더 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  12. 제 8항, 제 10항 또는 제 11항 중 어느 한 항에 있어서,
    상기 (c)단계에서, 상기 갱신지연 버퍼에 저장되어 있는 버퍼 엔트리들 중에서 상기 병합대상 페이지들로부터 파악된 기록가능공간에 해당하는 개수의 버퍼 엔트리를 병합가능 엔트리로 선정하고, 상기 병합가능 엔트리를 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 플래시 메모리에 기록될 인덱스 페이지를 구성하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  13. 제 8항, 제 10항 또는 제 11항 중 어느 한 항에 있어서,
    상기 (c)단계는,
    (c1) 상기 갱신지연 버퍼의 저장가능공간이 사전에 설정된 임계값보다 작아지면 상기 플래시 메모리로부터 레코드의 키값 및 레코드의 위치정보를 포함하는 복수개의 인덱스 엔트리로 이루어진 소정 개수의 인덱스 페이지를 병합대상 페이지로 선정하는 단계;
    (c2) 상기 갱신지연 버퍼에 저장되어 있는 버퍼 엔트리들 중에서 상기 병합대상 페이지들로부터 파악된 기록가능공간에 해당하는 개수의 버퍼 엔트리를 병합가능 엔트리로 선정하는 단계;
    (c3) 상기 병합가능 엔트리를 연산대상 데이터의 키값의 크기를 기준으로 상기 메인 메모리에 로딩된 인덱스 엔트리들 사이에 순차적으로 삽입하여 임시 인덱스 페이지를 구성하는 단계;
    (c4) 상기 임시 인덱스 페이지 중에서 상기 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행된 임시 인덱스 페이지에 대해 제1페이지 식별정보를 할당하고, 상기 병합가능 엔트리에 의한 삽입 또는 삭제연산이 수행되지 않은 임시 인덱스 페이지에 대해 제2페이지 식별정보를 할당하고, 나머지 임시 임덱스 페이지에 대해 제1페이지 식별정보를 할당하는 단계; 및
    (c5) 상기 제1페이지 식별정보가 할당된 임시 인덱스 페이지 중에서 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지의 이전 또는 이후에 위치하는 제2페이지 식별정보가 할당된 임시 인덱스 페이지에 제1페이지 식별정보를 다시 할당한 후 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지를 구성하는 엔트리들을 상기 제1페이지 식별정보가 할당된 임시 인덱스 페이지에 배분하여 상기 플래시 메모리에 기록될 인덱스 페이지를 구성하는 단계;를 포함하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  14. 제 13항에 있어서,
    상기 (c5)단계에서, 페이지 이용율이 사전에 설정된 기준이용율보다 낮은 임시 인덱스 페이지의 이전 또는 이후에 위치하는 제2페이지 식별정보가 할당된 임시 인덱스 페이지 중에서 페이지 이용율이 높은 페이지에 제1페이지 식별정보를 다시 할당하는 것을 특징으로 하는 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법.
  15. 제 8항 내지 제11항 중 어느 한 항에 기재된 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 방법을 컴퓨터에서 실행시키기 위한 프로그램을 기록한 컴퓨터로 읽을 수 있는 기록매체.
KR1020070071155A 2007-07-16 2007-07-16 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법 Expired - Fee Related KR100907477B1 (ko)

Priority Applications (1)

Application Number Priority Date Filing Date Title
KR1020070071155A KR100907477B1 (ko) 2007-07-16 2007-07-16 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
KR1020070071155A KR100907477B1 (ko) 2007-07-16 2007-07-16 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법

Publications (2)

Publication Number Publication Date
KR20090007926A KR20090007926A (ko) 2009-01-21
KR100907477B1 true KR100907477B1 (ko) 2009-07-10

Family

ID=40488380

Family Applications (1)

Application Number Title Priority Date Filing Date
KR1020070071155A Expired - Fee Related KR100907477B1 (ko) 2007-07-16 2007-07-16 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법

Country Status (1)

Country Link
KR (1) KR100907477B1 (ko)

Cited By (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101377923B1 (ko) * 2011-12-08 2014-03-24 한양대학교 에리카산학협력단 지연 갱신을 수행하는 ｂ-트리를 사용하여 플래시 메모리 내에 데이터를 저장하는 장치 및 방법
KR20160085035A (ko) * 2015-01-07 2016-07-15 에스케이텔레콤 주식회사 메모리제어장치 및 메모리제어장치의 동작 방법

Families Citing this family (5)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101949671B1 (ko) 2012-06-28 2019-04-25 삼성전자 주식회사 라이프 싸이클을 증가시킬 수 있는 저장 장치 및 그 동작 방법
KR101465447B1 (ko) * 2014-03-31 2014-12-10 성균관대학교산학협력단 외부 병합 정렬 방법, 외부 병합 정렬 시스템 및 외부 병합 정렬을 위한 분산 처리 시스템
CN110489380B (zh) * 2019-08-14 2024-02-13 腾讯科技（深圳）有限公司 一种数据处理方法、装置及设备
KR102102313B1 (ko) * 2019-11-27 2020-04-20 주식회사 리얼타임테크 인메모리 데이터베이스 기반의 시계열 데이터 관리시스템
CN113656406B (zh) * 2021-08-17 2025-01-24 北京金山云网络技术有限公司 一种索引页合并方法、装置、设备及介质

Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH1185609A (ja) 1997-09-09 1999-03-30 Mitsubishi Electric Corp 半導体記憶装置及びそのデータ管理方法
KR20060106993A (ko) * 2005-04-06 2006-10-13 주식회사 에스원 플래시 메모리 데이터 저장 방법
KR20070007264A (ko) * 2003-12-30 2007-01-15 쌘디스크 코포레이션 비순차 갱신 블록 관리를 구비한 비휘발성 메모리 및 방법
KR20070008403A (ko) * 2005-07-13 2007-01-17 삼성전자주식회사 복합 메모리를 구비하는 데이터 저장 시스템 및 그 동작방법

Patent Citations (4)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH1185609A (ja) 1997-09-09 1999-03-30 Mitsubishi Electric Corp 半導体記憶装置及びそのデータ管理方法
KR20070007264A (ko) * 2003-12-30 2007-01-15 쌘디스크 코포레이션 비순차 갱신 블록 관리를 구비한 비휘발성 메모리 및 방법
KR20060106993A (ko) * 2005-04-06 2006-10-13 주식회사 에스원 플래시 메모리 데이터 저장 방법
KR20070008403A (ko) * 2005-07-13 2007-01-17 삼성전자주식회사 복합 메모리를 구비하는 데이터 저장 시스템 및 그 동작방법

Cited By (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
KR101377923B1 (ko) * 2011-12-08 2014-03-24 한양대학교 에리카산학협력단 지연 갱신을 수행하는 ｂ-트리를 사용하여 플래시 메모리 내에 데이터를 저장하는 장치 및 방법
KR20160085035A (ko) * 2015-01-07 2016-07-15 에스케이텔레콤 주식회사 메모리제어장치 및 메모리제어장치의 동작 방법
KR102263800B1 (ko) * 2015-01-07 2021-06-10 에스케이텔레콤 주식회사 메모리제어장치 및 메모리제어장치의 동작 방법

Also Published As

Publication number Publication date
KR20090007926A (ko) 2009-01-21

Similar Documents

Publication Publication Date Title
US11243911B2 (en) Method and apparatus for fault-tolerant memory management
US6571261B1 (en) Defragmentation utility for a shared disk parallel file system across a storage area network
CN100565530C (zh) 一种快照系统及其使用方法
US7930559B1 (en) Decoupled data stream and access structures
US7640262B1 (en) Positional allocation
JP6205650B2 (ja) 不均等アクセス・メモリにレコードを配置するために不均等ハッシュ機能を利用する方法および装置
US7610468B2 (en) Modified buddy system memory allocation
US7673099B1 (en) Affinity caching
US7720892B1 (en) Bulk updates and tape synchronization
US7933938B2 (en) File storage system, file storing method and file searching method therein
KR100907477B1 (ko) 플래시 메모리에 저장된 데이터의 인덱스 정보 관리 장치및 방법
KR20070060070A (ko) 최적화된 순차적인 클러스터 관리용 에프에이티 분석
CN111522507B (zh) 一种低延迟的文件系统地址空间管理方法、系统及介质
JP2001249844A (ja) 永続的且つロバストな記憶割当てシステム及び方法
JP2001249835A (ja) 永続的且つロバストなメモリ管理のためのシステム及び方法
KR20210058118A (ko) CaseDB: 엣지컴퓨팅을 위한 저비용 Put-Intensive 키-벨류 저장장치
US20240028560A1 (en) Directory management method and system for file system based on cuckoo hash and storage medium
US11144508B2 (en) Region-integrated data deduplication implementing a multi-lifetime duplicate finder
CN103530067A (zh) 一种数据操作的方法和设备
Lee et al. An efficient buffer management scheme for implementing a B-tree on NAND flash memory
KR100982591B1 (ko) 단계적 인덱싱을 위한 파일 시스템, 메인 기억장치 및플래시 기억장치 그리고 상기 단계적 인덱싱을 통한 데이터관리 방법
US10877881B2 (en) In-place garbage collection of a sharded, replicated distributed state machine based on mergeable operations
KR100859989B1 (ko) 플래시 메모리의 공간정보 관리장치 및 그 방법
CN120196288B (en) Data storage method, system, electronic equipment and storage medium
CN120196288A (zh) 一种数据存储方法、系统、电子设备及存储介质

Legal Events

Date Code Title Description
A201 Request for examination
PA0109 Patent application

St.27 status event code: A-0-1-A10-A12-nap-PA0109

PA0201 Request for examination

St.27 status event code: A-1-2-D10-D11-exm-PA0201

D13-X000 Search requested

St.27 status event code: A-1-2-D10-D13-srh-X000

D14-X000 Search report completed

St.27 status event code: A-1-2-D10-D14-srh-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-3-3-R10-R18-oth-X000

E902 Notification of reason for refusal
PE0902 Notice of grounds for rejection

St.27 status event code: A-1-2-D10-D21-exm-PE0902

PG1501 Laying open of application

St.27 status event code: A-1-1-Q10-Q12-nap-PG1501

P11-X000 Amendment of application requested

St.27 status event code: A-2-2-P10-P11-nap-X000

P13-X000 Application amended

St.27 status event code: A-2-2-P10-P13-nap-X000

E701 Decision to grant or registration of patent right
PE0701 Decision of registration

St.27 status event code: A-1-2-D10-D22-exm-PE0701

GRNT Written decision to grant
PR0701 Registration of establishment

St.27 status event code: A-2-4-F10-F11-exm-PR0701

PR1002 Payment of registration fee

St.27 status event code: A-2-2-U10-U11-oth-PR1002

Fee payment year number: 1

PG1601 Publication of registration

St.27 status event code: A-4-4-Q10-Q13-nap-PG1601

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 4

FPAY Annual fee payment

Payment date: 20130701

Year of fee payment: 5

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 5

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R11-asn-PN2301

PN2301 Change of applicant

St.27 status event code: A-5-5-R10-R14-asn-PN2301

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

FPAY Annual fee payment

Payment date: 20140624

Year of fee payment: 6

PR1001 Payment of annual fee

St.27 status event code: A-4-4-U10-U11-oth-PR1001

Fee payment year number: 6

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

LAPS Lapse due to unpaid annual fee
PC1903 Unpaid annual fee

St.27 status event code: A-4-4-U10-U13-oth-PC1903

Not in force date: 20150707

Payment event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

PC1903 Unpaid annual fee

St.27 status event code: N-4-6-H10-H13-oth-PC1903

Ip right cessation event data comment text: Termination Category : DEFAULT_OF_REGISTRATION_FEE

Not in force date: 20150707

P22-X000 Classification modified

St.27 status event code: A-4-4-P10-P22-nap-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000

R18-X000 Changes to party contact information recorded

St.27 status event code: A-5-5-R10-R18-oth-X000