제2 항에 있어서,상기 컨트롤러는,상기 최상위 계층에서 1 회의 조회로서 상기 논리 주소에 맵핑된 상기 물리 주소를 획득하고,상기 최상위 계층 이외의 상기 계층에서 적어도 1 회의 조회로서 상기 논리 주소에 맵핑된 상기 물리 주소를 획득 가능한,SSD(Solid State Drive) 장치.

호스트와 연결하는 인터페이스 로직;데이터가 저장되는 비휘발성 메모리; 및상기 비휘발성 메모리를 제어하는 컨트롤러를 포함하고,상기 컨트롤러는 상기 호스트가 제공한 논리 주소를 상기 비휘발성 메모리에 대한 물리 주소로 변환하고, 상기 물리 주소에 기반하여 상기 비휘발성 메모리에 액세스하고,상기 컨트롤러는 계층적 구조인 LSM-tree(log-structured merge tree)로 구성된 복수의 계층에 저장된 색인(indexing) 정보에 기반하여 상기 논리 주소를 상기 물리 주소로 변환하고,상기 LSM-tree의 복수의 상기 계층 중 적어도 두 개의 상기 계층은 서로 다른 방식으로 상기 논리 주소 및 상기 논리 주소에 대응하는 상기 물리 주소의 맵핑에 기반한 상기 색인 정보를 저장하는,SSD(Solid State Drive) 장치.

제1 항에 있어서,상기 LSM-tree의 복수의 상기 계층 중 최상위 계층은 상기 논리 주소와 상기 논리 주소에 맵핑되는 상기 물리 주소를 상기 색인 정보로서 저장하고, 상기 최상위 계층 이외의 계층들은 상기 논리 주소에 맵핑되는 상기 물리 주소를 추측 방식으로 추정하는 상기 색인 정보를 저장하는,SSD(Solid State Drive) 장치.

제2 항에 있어서,상기 최상위 계층 이외의 계층들은,블룸 필터(Bloom filter)에 기반하여 상기 물리 주소를 확률적으로 추측하는 근사 인덱싱(approximate indexing) 기반의 상기 색인 정보를 저장하는 적어도 하나의 중간 계층; 및Piece-wise linear regression(PLR) 모델에 기반하여 상기 물리 주소를 확률적으로 추측하는 근사 인덱싱 기반의 상기 색인 정보를 저장하는 적어도 하나의 하위 계층으로 구성되는,SSD(Solid State Drive) 장치.

제3 항에 있어서,상기 중간 계층은 상기 논리 주소의 해시(hash) 값을 저장하고, 상기 컨트롤러는 상기 중간 계층에서 제1 논리 주소에 대응하는 제1 물리 주소를 조회하는 경우, 상기 컨트롤러는 상기 중간 계층의 상기 색인 정보에 기반하여 상기 제1 논리 주소의 해시 값과 동일한 해시 값을 갖는 블룸 필터에 대응하는 제1 추정 물리 주소를 획득하는,SSD(Solid State Drive) 장치.

제3 항에 있어서,상기 컨트롤러는 쓰기 모드에서 상기 중간 계층에 제1 논리 주소와 상기 제1 논리 주소에 대응하는 제1 물리 주소의 맵핑에 기반한 상기 색인 정보를 저장하는 경우,상기 제1 논리 주소에 맵핑될 상기 제1 물리 주소에 대응하는 블룸 필터에 상기 제1 논리 주소의 해시 값을 저장하고, 상기 제1 물리 주소에 대응하는 OOB 영역(Out-of-band area)에 상기 제1 논리 주소를 저장하고, 상기 제1 물리 주소에 데이터를 저장하는,SSD(Solid State Drive) 장치.

제3 항에 있어서,상기 컨트롤러는 상기 하위 계층에서 제2 논리 주소에 대응하는 제2 물리 주소를 조회하는 경우, 상기 컨트롤러는 상기 하위 계층의 상기 색인 정보에 기반하여 제2 논리 주소에 대응하는 제2 물리 주소를 기준으로 미리 설정된 에러 범위 이내에 존재하는 제2 추정 물리 주소를 획득하는,SSD(Solid State Drive) 장치.

제3 항에 있어서,상기 하위 계층은 제2 논리 주소와 상기 제2 논리 주소에 대응하는 제2 물리 주소의 상기 색인 정보를 저장하는 경우,상기 제2 논리 주소에 기반하여 상기 제2 물리 주소를 기준으로 미리 설정된 에러 범위 이내에 존재하는 제2 추정 물리 주소를 산출 가능한 상기 PLR 모델을 저장하는, SSD(Solid State Drive) 장치.

제8 항에 있어서,상기 하위 계층은, 서로 다른 상기 논리 주소들의 집합에 대해 각각 추정 물리 주소를 산출 가능한 상기 PLR 모델로서, 서로 기울기 및 절편이 다른 복수의 상기 PLR 모델을 저장하는,SSD(Solid State Drive) 장치.

제1 항에 있어서,복수의 상기 계층 각각은 상기 색인 정보를 유지하는 적어도 하나의 런(run)을 포함하고, 상기 컨트롤러는 제1 논리 주소 변환을 위해서 상기 제1 논리 주소에 대응하는 상기 색인 정보가 존재하는 상기 런의 정보가 저장된 숏컷 테이블(shortcut table)을 조회하고, 상기 숏컷 테이블에서 조회된 상기 런의 복수의 상기 색인 정보에서 상기 제1 논리 주소에 대응하는 상기 색인 정보를 조회하는,SSD(Solid State Drive) 장치.

제10 항에 있어서,상기 런은 복수의 런 청크(run chunk)로 구성되고, 상기 런 청크는 상기 비휘발성 메모리의 메모리 블록과 크기가 동일하고,상기 컨트롤러는 상기 런 청크와 상기 메모리 블록 사이의 맵핑 정보를 저장하는 정렬 테이블(sorted table)에 기반하여, 상기 색인 정보에 대응하는 상기 물리 주소를 조회하는, SSD(Solid State Drive) 장치.

제1 항에 있어서,복수의 상기 계층은 계층 순서대로 최상위 계층, 적어도 하나의 중간 계층 및 적어도 하나의 하위 계층으로 구성되고, 인접한 두 계층 중 아래의 계층은 위의 계층보다 미리 설정된 배수만큼 크고, 상기 계층 각각은 상기 색인 정보를 저장하는 적어도 하나의 런(run)을 포함하고, 상기 런은 상기 색인 정보의 상기 논리 주소 순서로 정렬하여 복수의 상기 색인 정보를 저장하고,상기 컨트롤러는 상기 계층 중 어느 한 계층의 모든 런이 포화된 경우, 포화된 상기 계층의 적어도 하나의 색인 정보를 상기 최상위 계층, 상기 중간 계층 및 상기 하위 계층의 순서대로 아래에 위치한 상기 계층으로 이동시키는,SSD(Solid State Drive) 장치.

호스트와 연결하는 인터페이스 로직;데이터가 저장되는 비휘발성 메모리; 및상기 비휘발성 메모리를 제어하는 컨트롤러를 포함하는 SSD(Solid State Drive) 장치의 동작 방법으로서,상기 컨트롤러가 상기 호스트가 전송한 논리 주소를 제공 받는 단계;상기 컨트롤러가 제공 받은 상기 논리 주소를 계층적 구조인 LSM-tree(log-structured merge tree)로 구성된 복수의 계층에 저장된 색인(indexing) 정보에 기반하여 상기 비휘발성 메모리에 대한 물리 주소로 변환하는 단계; 및상기 컨트롤러가 상기 물리 주소에 기반하여 상기 비휘발성 메모리에 액세스하는 단계를 포함하고,상기 LSM-tree의 복수의 상기 계층 중 적어도 두 개의 상기 계층은 서로 다른 방식으로 상기 논리 주소 및 상기 논리 주소에 대응하는 상기 물리 주소의 맵핑에 기반한 상기 색인 정보를 저장하는,SSD(Solid State Drive) 장치의 동작 방법.

제13 항에 있어서,상기 물리 주소로 변환하는 단계는,상기 컨트롤러가 상기 LSM-tree의 복수의 상기 계층 중 상기 논리 주소와 상기 논리 주소에 맵핑되는 상기 물리 주소를 페어(pair) 형태의 상기 색인 정보로서 저장하는 최상위 계층을 조회하는 단계, 또는 상기 컨트롤러가 상기 논리 주소에 맵핑되는 상기 물리 주소를 추측 방식으로 추정하는 상기 색인 정보를 저장하는 상기 최상위 계층 이외의 계층들을 조회하는 단계를 포함하는,SSD(Solid State Drive) 장치의 동작 방법.

제14 항에 있어서,상기 컨트롤러가 상기 최상위 계층 이외의 계층들을 조회하는 단계는,상기 컨트롤러가 블룸 필터(Bloom filter)에 기반하여 상기 물리 주소를 확률적으로 추측하는 근사 인덱싱(approximate indexing) 기반의 상기 색인 정보를 저장하는 적어도 하나의 중간 계층을 조회하는 단계, 또는 상기 컨트롤러가 Piece-wise linear regression(PLR) 모델에 기반하여 상기 물리 주소를 확률적으로 추측하는 근사 인덱싱 기반의 상기 색인 정보를 저장하는 적어도 하나의 하위 계층을 조회하는 단계를 포함하는,SSD(Solid State Drive) 장치의 동작 방법.

제15 항에 있어서,상기 중간 계층은 상기 논리 주소의 해시(hash) 값을 저장하고,상기 컨트롤러가 상기 중간 계층을 조회하는 단계는,상기 컨트롤러가 상기 중간 계층의 상기 색인 정보에 기반하여 상기 제1 논리 주소의 해시 값과 동일한 해시 값을 갖는 블룸 필터에 대응하는 제1 추정 물리 주소를 획득하는 단계를 포함하는,SSD(Solid State Drive) 장치의 동작 방법.

제15 항에 있어서,상기 컨트롤러는 쓰기 모드에서 상기 중간 계층에 제1 논리 주소와 상기 제1 논리 주소에 대응하는 제1 물리 주소의 맵핑에 기반한 상기 색인 정보를 저장하는 경우,상기 컨트롤러가 상기 제1 논리 주소에 맵핑될 상기 제1 물리 주소에 대응하는 블룸 필터에 상기 제1 논리 주소의 해시 값을 저장하는 단계; 및 상기 컨트롤러가 상기 제1 물리 주소에 대응하는 OOB 영역(Out-of-band area)에 상기 제1 논리 주소를 저장하고, 상기 제1 물리 주소에 데이터를 저장하는 단계를 포함하는,SSD(Solid State Drive) 장치의 동작 방법.

제15 항에 있어서,상기 컨트롤러는 상기 하위 계층에서 제2 논리 주소에 대응하는 제2 물리 주소를 조회하는 경우, 상기 컨트롤러가 상기 하위 계층을 조회하는 단계는,상기 컨트롤러가 상기 하위 계층의 상기 색인 정보에 기반하여 제2 논리 주소에 대응하는 제2 물리 주소를 기준으로 미리 설정된 에러 범위 이내에 존재하는 제2 추정 물리 주소를 획득하는 단계를 포함하는,SSD(Solid State Drive) 장치의 동작 방법.

제15 항에 있어서,상기 컨트롤러가 상기 하위 계층에 제2 논리 주소와 상기 제2 논리 주소에 대응하는 제2 물리 주소의 상기 색인 정보를 저장하는 경우,상기 컨트롤러가 상기 제2 논리 주소에 기반하여 상기 제2 물리 주소를 기준으로 미리 설정된 에러 범위 이내에 존재하는 제2 추정 물리 주소를 산출 가능한 상기 PLR 모델을 저장하거나 변경하는 단계를 포함하는, SSD(Solid State Drive) 장치의 동작 방법.

제13 항에 있어서,복수의 상기 계층 각각은 상기 색인 정보를 유지하는 적어도 하나의 런(run)을 포함하고, 상기 물리 주소로 변환하는 단계는,상기 컨트롤러가 제1 논리 주소 변환을 위해서 상기 제1 논리 주소에 대응하는 상기 색인 정보가 존재하는 상기 런의 정보가 저장된 숏컷 테이블(shortcut table)을 조회하는 단계; 및상기 컨트롤러가 상기 숏컷 테이블에서 조회된 상기 런의 복수의 상기 색인 정보에서 상기 제1 논리 주소에 대응하는 상기 색인 정보를 조회하는 단계를 포함하는,SSD(Solid State Drive) 장치의 동작 방법.