제 8 항에 있어서, 검색 키의 검색 요청 또는 삽입 키의 삽입 요청이 수신되면, 검색 키 또는 삽입 키를 상기 생성된 이진 탐색 트리의 루트 노드 위치 노드와 비교하여 서브 노드를 결정하는 단계를 반복 수행하여 상기 생성된 스킵 리스트의 최상위 연결 리스트의 노드를 찾아내는 단계;를 더 포함하는, 방법.

하나의 프로세서들, 및상기 하나 이상의 프로세서들에 의해 실행되는 하나 이상의 프로그램들을 저장하는 메모리를 구비한 컴퓨팅 장치에서 수행되는 방법으로서, 적어도 하나 이상의 연결 리스트로 구성되는 스킵 리스트를 생성하는 단계; 및상기 생성하는 단계에서 구성된 스킵 리스트의 연결 리스트들 중 최상위 연결 리스트에 포함되는 노드에 검색 가속을 적용하기 위한 이진 탐색 트리를 생성하는 단계;를 포함하는, 방법.

제 1 항에 있어서, 상기 이진 탐색 트리를 생성하는 단계는, 생성된 이진 탐색 트리 용량과 이진 트리 확보 가능한 캐시 공간을 비교하여 이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 미만이면 이진 탐색 트리를 생성하는, 방법.

제 2 항에 있어서, 상기 이진 탐색 트리를 생성하는 단계는, 생성된 이진 탐색 트리 용량과 이진 트리 확보 가능한 캐시 공간을 비교하여 이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 이상이면, 최상위 연결 리스트에 포함되는 노드의 적어도 일부를 선별하여 이진 탐색 트리를 생성하는, 방법.

제 3 항에 있어서, 상기 이진 탐색 트리를 생성하는 단계는, 최상위 연결 리스트에 포함되는 노드들 중 확률적으로 적어도 일부를 선별하는, 방법.

제 3 항에 있어서, 상기 이진 탐색 트리를 생성하는 단계는, 최상위 연결 리스트에 포함되는 노드들 중 사용 빈도가 높은 순으로 적어도 일부를 선별하는, 방법.

제 1 항에 있어서, 상기 스킵 리스트를 생성하는 단계에서 구성된 스킵 리스트의 연결 리스트들 중 최상위 연결 리스트에 신규 노드가 추가되면, 이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 미만일 경우에 신규 노드를 이진 탐색 트리에 추가하는 노드 추가 단계;를 더 포함하는, 방법.

제 6 항에 있어서, 상기 노드 추가 단계는,이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 이상이면 배치(batch) 형식으로 신규 노드를 이진 탐색 트리에 추가하는, 방법.

제 7 항에 있어서, 상기 노드 추가 단계는, 신규 노드를 배치(batch)에 우선 저장하고, 배치에 누적되는 노드가 미리 설정된 값에 도달하면, 기존 노드들과 배치에 누적된 적어도 하나 이상의 신규 노드들을 기반으로 정책에 따른 선별 작업을 거쳐 선별된 노드들로 이진 탐색 트리를 재구성하는, 방법.

제 8 항에 있어서, 상기 미리 설정된 값은 캐시 크기를 모두 채울 수 있는 노드 개수가 디폴트값인, 방법.

제 8 항에 있어서, 이진 탐색 트리를 재구성하는 동안 노드 검색 또는 삽입 요청이 수신되면, 상기 생성된 스킵 리스트에 의해서만 검색 또는 삽입 기능을 수행하는, 방법.

하나 이상의 프로세서들, 및상기 하나 이상의 프로세서들에 의해 실행되는 하나 이상의 프로그램들을 저장하는 메모리를 구비한 컴퓨팅 장치로서,적어도 하나 이상의 연결 리스트로 구성되는 스킵 리스트를 생성하는 스킵 리스트 생성 모듈; 및상기 스킵 리스트 생성부에서 구성된 스킵 리스트의 연결 리스트들 중 최상위 연결 리스트에 포함되는 노드에 검색 가속을 적용하기 위한 이진 탐색 트리를 생성하는 가속 생성 모듈;을 포함하는, 장치.

제 12 항에 있어서, 상기 가속 생성 모듈은,생성된 이진 탐색 트리 용량과 이진 트리가 확보 가능한 캐시 공간을 비교하여 이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 미만이면 이진 탐색 트리를 생성하는, 장치.

제 13 항에 있어서, 상기 가속 생성 모듈은,생성된 이진 탐색 트리 용량과 이진 트리 확보 가능한 캐시 공간을 비교하여 이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 이상이면, 최상위 연결 리스트에 포함되는 노드의 적어도 일부를 선별하여 이진 탐색 트리를 생성하는, 장치.

제 14항에 있어서, 상기 가속 생성 모듈은,최상위 연결 리스트에 포함되는 노드들 중 확률적으로 적어도 일부를 선별하는, 장치.

제 14 항에 있어서, 상기 가속 생성 모듈은,최상위 연결 리스트에 포함되는 노드들 중 사용 빈도가 높은 순으로 적어도 일부를 선별하는, 장치.

제 12 항에 있어서, 상기 스킵 리스트 생성 모듈에서 구성된 스킵 리스트의 연결 리스트들 중 최상위 연결 리스트에 신규 노드가 추가되면, 이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 미만일 경우에 신규 노드를 이진 탐색 트리에 추가하는 노드 추가 모듈;을 더 포함하는, 장치.

제 17 항에 있어서, 상기 노드 추가 모듈은,이진 탐색 트리 용량이 이진 트리 확보 가능한 캐시 공간 이상이면 배치(batch) 형식으로 신규 노드를 이진 탐색 트리에 추가하는, 장치.

제 18 항에 있어서, 상기 노드 추가 모듈은, 신규 노드를 배치(batch)에 우선 저장하고, 배치에 누적되는 노드가 미리 설정된 값에 도달하면, 기존 노드들과 배치에 누적된 적어도 하나 이상의 신규 노드들을 기반으로 정책에 따른 선별 작업을 거쳐 선별된 노드들로 이진 탐색 트리를 재구성하는, 장치.

비일시적 컴퓨터 판독 가능한 저장 매체(non-transitory computer readable storage medium)에 저장된 컴퓨터 프로그램으로서, 상기 컴퓨터 프로그램은 하나 이상의 명령어들을 포함하고, 상기 명령어들은 하나 이상의 프로세서들을 갖는 컴퓨터 장치에 의해 실행될 때, 상기 컴퓨터 장치로 하여금, 적어도 하나 이상의 연결 리스트로 구성되는 스킵 리스트를 생성하는 단계; 및상기 생성하는 단계에서 구성된 스킵 리스트의 연결 리스트들 중 최상위 연결 리스트에 포함되는 노드에 검색 가속을 적용하기 위한 이진 탐색 트리를 생성하는 단계;를 수행하도록 하는, 컴퓨터 프로그램.