| 1 |
1
하나 이상의 노드들을 포함하는 B-트리를 저장하는 플래시 메모리;상기 하나 이상의 노드들 각각을 선택적으로 적재하는 메모리; 및상기 플래시 메모리 및 상기 메모리를 제어하는 제어부를 포함하고, 상기 제어부는 상기 B-트리에 대한 삽입 연산 시 상기 하나 이상의 노드들 중 상기 삽입 연산에 의해 변경이 일어나는 리프 노드와 상기 B-트리의 루트 노드로부터 상기 리프 노드까지의 경로 내에 있는 상기 리프 노드의 조상 노드들을 하나 이상의 변경 노드들로 식별하여, 상기 식별된 하나 이상의 변경 노드들 모두를 상기 메모리 내에 적재하고, 상기 식별된 하나 이상의 변경 노드들을 저장하는 상기 플래시 메모리 내의 페이지들을 유효하지 않은(invalid) 페이지들로 설정하며,상기 삽입 연산에 따른 변경을 상기 메모리 내에 적재된 모든 노드들에게 적용함으로써 상기 식별된 하나 이상의 변경 노드들 모두에 대하여 상기 플래시 메모리로의 쓰기 연산을 지연시키며,상기 메모리 내에 적재된 노드의 모든 엔트리들 내에 키들이 저장된 이후에, 상기 적재된 노드를 상기 플래시 메모리 내에 저장하고,상기 메모리 내에 적재된 노드가 상기 플래시 메모리 내의 노드와 교환될 때, 상기 적재된 노드를 상기 플래시 메모리 내에 저장하거나, 상기 하나 이상의 노드들 중 리프 노드가 상기 메모리 내에 적재될 때, 상기 메모리 내에 적재된 노드들 중 다른 리프 노드를 상기 플래시 메모리 내에 저장하는, 플래시 메모리 기반 저장 장치
|
| 2 |
2
제1항에 있어서,상기 B-트리는 상기 플래시 메모리의 인덱스 구조를 나타내는, 플래시 메모리 기반 저장 장치
|
| 3 |
3
삭제
|
| 4 |
4
삭제
|
| 5 |
5
삭제
|
| 6 |
6
삭제
|
| 7 |
7
삭제
|
| 8 |
8
제1항에 있어서,상기 제어부는 순차적인 삽입 연산들을 감지하고, 상기 삽입 연산이 상기 순차적인 삽입 연산들 중 하나이면 상기 적재된 노드들의 분할 없이 상기 삽입 연산에 따른 상기 변경을 적용하는, 플래시 메모리 기반 저장 장치
|
| 9 |
9
제1항에 있어서,상기 제어부는 일정한 조건이 만족될 때, 상기 메모리 내에 적재된 모든 노드들을 상기 플래시 메모리 내에 저장하는, 플래시 메모리 기반 저장 장치
|
| 10 |
10
제9항에 있어서,상기 조건은 상기 하나 이상의 노드들 중 상기 메모리 내에 적재된 루트 노드 내의 키들의 개수가 변경되는 것인, 플래시 메모리 기반 저장 장치
|
| 11 |
11
플래시 메모리 내에 저장된 하나 이상의 노드들을 포함하는 B-트리를 관리하는 방법에 있어서,특정한 키를 상기 B-트리 내에 삽입하는 삽입 연산에 의해 변경이 일어나는 리프 노드와 상기 B-트리의 루트 노드로부터 상기 리프 노드까지의 경로 내에 있는 상기 리프 노드의 조상 노드들을 하나 이상의 변경 노드들로 식별하는 단계;상기 식별된 하나 이상의 변경 노드들을 저장하는 상기 플래시 메모리 내의 페이지들을 유효하지 않은(invalid) 페이지들로 설정하며, 상기 하나 이상의 변경 노드들 모두를 메모리 내에 적재하는 단계;상기 삽입 연산에 따른 변경을 상기 메모리 내에 적재된 모든 노드들에게 적용함으로써 상기 식별된 하나 이상의 변경 노드들 모두에 대하여 상기 플래시 메모리로의 쓰기 연산을 지연시키는 단계; 및상기 메모리 내에 적재된 노드의 모든 엔트리들 내에 키들이 저장된 이후에, 상기 적재된 노드를 상기 플래시 메모리 내에 저장하는 단계를 포함하고,상기 적재된 노드를 상기 플래시 메모리 내에 저장하는 단계는상기 메모리 내에 적재된 노드가 상기 플래시 메모리 내의 노드와 교환될 때, 상기 적재된 노드를 상기 플래시 메모리 내에 저장하거나, 상기 하나 이상의 노드들 중 리프 노드가 상기 메모리 내에 적재될 때, 상기 메모리 내에 적재된 노드들 중 다른 리프 노드를 상기 플래시 메모리 내에 저장하는 단계를 포함하는, 플래시 메모리 내에 저장된 데이터 관리 방법
|
| 12 |
12
삭제
|
| 13 |
13
삭제
|
| 14 |
14
제11항에 있어서,상기 삽입 연산이 순차적인 삽입 연산들 중 하나인 경우 상기 변경은 상기 메모리에 적재된 노드의 분할 없이 상기 메모리 내에 적재된 노드들에게 적용되는, 플래시 메모리 내에 저장된 데이터 관리 방법
|
| 15 |
15
제11항에 있어서,일정한 조건이 만족될 경우, 메모리 내에 적재된 모든 노드들을 플래시 메모리 내에 저장하는 단계를 더 포함하는, 플래시 메모리 내에 저장된 데이터 관리 방법
|
