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