cdb(소프트웨어)
cdb (software) |
|
cdb는 "constant database"의 줄임말로 Daniel J. Bernstein에 의해 작성된 라이브러리와 데이터 형식을 모두 나타냅니다.cdb는 온디스크 관련 배열로 기능하여 키를 값에 매핑하고 하나의 키에 대해 여러 값을 저장할 수 있습니다.상수 데이터베이스에서는 작성과 읽기 두 가지 작업만 허용합니다.두 작업 모두 매우 빠르고 신뢰성이 높아지도록 설계되었습니다.데이터베이스는 사용 중 변경되지 않으므로 여러 프로세스가 잠금 없이 단일 데이터베이스에 액세스할 수 있습니다.또한 모든 수정이 대체 데이터베이스를 생성하므로 UNIX 파일 시스템 시멘틱스를 활용하여 신뢰성을 보장할 수 있습니다.
레코드 위치, 키 및 값 길이, 해시 값은 32비트이므로 4기가바이트에 [1]적합해야 합니다.cdb는 djbdns, fastforward, mess822, qmail 및 ucspi-model에서 사용되며 매우 효율적이고 신뢰성이 높으며 단순한 데이터 액세스를 제공합니다.
구조.
데이터베이스는 단일 컴퓨터 파일에 전체 데이터 세트(예를 들어 단일 연관 배열)를 포함합니다.이것은 고정 크기의 헤더, 데이터 및 해시 테이블 세트의 세 부분으로 구성됩니다.검색은 정확한 키에 대해서만 설계되지만 전체 데이터베이스를 검색하여 다른 유형의 검색을 수행할 수 있습니다.룩업은 다음 알고리즘을 사용하여 수행됩니다.
- 키를 해시합니다.
- 이 레코드를 어느 해시 테이블과 슬롯에 배치할지를 결정합니다.
- 해시 테이블에서 지정된 슬롯을 테스트합니다.
- 슬롯이 비어 있으면 레코드는 존재하지 않습니다.검색을 중단합니다.
- 슬롯의 해시가 키의 해시와 일치하면 레코드를 찾습니다.키를 읽고 비교합니다.일치하는 경우 데이터가 발견되었으므로 검색을 종료합니다.
- 레코드는 이 슬롯에 없습니다.필요에 따라서, 해시 테이블의 선두로 둘러싸면서, 다음의 슬롯으로 진행됩니다.
여러 값을 가진 키를 검색할 경우 다음 슬롯에서 검색을 다시 시작하는 것만으로 추가 값을 찾을 수 있습니다.
포맷
모든 번호(오프셋, 길이 및 해시 값)는 부호 없는 32비트 정수이며 little endian 형식으로 저장됩니다.키와 데이터는 불투명한 바이트 문자열로 간주되며 특별한 취급은 없습니다.
데이터베이스 선두에 있는 고정 크기 헤더는 파일 내의 위치와 슬롯 내의 길이를 나열하여 256개의 해시 테이블을 나타냅니다.데이터는 일련의 레코드로 저장되며 각각 키 길이, 데이터 길이, 키 및 데이터가 저장됩니다.정렬 또는 정렬 규칙은 없습니다.레코드 뒤에는 길이가 다른 256개의 해시 테이블이 계속됩니다.0은 유효한 길이이므로 데이터베이스에 물리적으로 저장되어 있는 해시 테이블은 256개 미만일 수 있지만 256개의 테이블로 간주됩니다.해시 테이블에는 일련의 슬롯이 있으며 각 슬롯에는 해시 값과 레코드 오프셋이 포함됩니다."빈 슬롯"의 오프셋은 0입니다.
해시는 부호 없는 32비트 정수이며 5381의 값으로 시작합니다.키의 각 바이트에 대해 현재 해시에 33을 곱한 다음 키의 현재 바이트와 XOR을 곱합니다.오버플로 비트는 폐기됩니다.슬롯과 테이블은 해시로부터 3차적으로 계산됩니다.타깃 테이블은 단순히 해시 중 최하위8비트(즉, 해시 모듈로 256)이며, 테이블 내의 슬롯은 해시 모듈로 테이블 길이(즉, 해시를 256 모듈로 테이블 길이)의 나머지 비트입니다.
도서관
공식 CDB 라이브러리 코드는 퍼블릭도메인입니다.개별 소스 파일은 퍼블릭도메인 djbdns 패키지로 사용할 수 있습니다.그러나 CDB 패키지의 나머지 부분은 라이선스가 필요 없는 소프트웨어였기 때문에 말 그대로 배포해야 합니다.이 포맷의 특이한 라이센스와 단순성으로 인해 다른 사람들은 라이브러리를 다시 구현하고 [2]퍼블릭 도메인에서 사용할 수 있는 Michael Tokarev의 Tiny CDB 라이브러리와 같은 더 일반적인 조건으로 출시하게 되었습니다.
2009년에는 모든 CDB가 퍼블릭 [3]도메인에 포함되었습니다.
특히 cdb의 작성자는 cdb를 공유 라이브러리로 사용할 의도가 없습니다.이는 Berkeley DB와 같은 거의 모든 유사한 dbm-like 데이터베이스와 다릅니다.
레퍼런스
- ^ CDB 사양
- ^ "TinyCDB - a Constant DataBase". www.corpit.ru. Retrieved 2016-12-12.
- ^ "Frequently asked questions from distributors".
