해시 테이블 조회를 위해 이동하기로 결정한 것처럼 빠르게 검색해야하는 레코드 테이블이 있습니다.다중 인덱스 해시 테이블 구현
이제는 여러 키를 기반으로 레코드를 조회해야한다는 문제가있었습니다.
예를 들어, 아래의 4 키는 모두 동일한 레코드를 가리켜 야합니다.
key1 -> a,b,c,d,e
key2 -> a,b,d
key3 -> a,b,e
key4 -> c
문제 # 1 이 패턴은 여러 개의 키가 지정된 데이터베이스 조회에 유사성을 보여 주었다. B- 트리 데이터 구조는 다중 해시 테이블 설계보다 사용하기에 최적일까요?
문제 # 2 특수한 트라이가 문제에 더 잘 맞는지 여부. 기본 구현에서는 모든 키 a + b + c + d + e를 검색 키로 요구합니다. + b + d를 조회해야한다면이 마스터 키를 사용하여 올려다 보면서 C & e를 건너 뛸 수 있습니다. 그렇다면이 아이디어가 효과가 있느냐, 이미 밖으로 나가고 있는가?
문제 # 3 또 다른 아이디어는 내 테이블에 물건을 삽입했는지, 아니면 병렬로 각 레코드에 인덱스가있는 다른 룩업 테이블을 구축했는지입니다. 그런 식으로 각 키에 대해 여러 개의 마스크를 사용할 수 있으며이 조회 테이블에서 일치하는 레코드를 검색 할 수 있습니다. CAM 테이블과 비슷한 것 같습니다. 그러나 전체 테이블을 스캔해야한다면 성능이 떨어질 수 있습니다. 해시 테이블 + 인덱싱 로직을 함께 사용하여 속도와 최적의 메모리 사용량을 제공 할 수 있습니까?
지금까지 부스트 멀티 인덱스, uthash, trie 등을 사용하여 4 가지 문제는 모두 해결했지만 아직까지는 성공하지 못한 디자인을 시도했습니다. 나는 멀티 인덱스를 향상시키는 것을 좋아했지만, 그것은 내가 사용할 수없는 문제의 자신의 몫을 가지고있다.
프로그래밍을 위해 C 언어를 사용하지만 디자인을 테스트하는 데 Java, PHP, Python과 같은 다른 언어도 사용할 수 있습니다.
이 문제를 해결하기위한 다른 아이디어는 크게 감사하겠습니다. 내가 달성하고자하는 솔루션의
의사 코드 :
/* Keys */
struct key1_s {
int src;
int dst;
char name[10];
int t1;
int t2;
};
struct key2_s {
int src;
int dst;
char name[10];
};
struct key3_s {
int src;
int dst;
int t1;
};
struct key4_s {
int src;
int dst;
int t2;
};
/* Record */
struct record_s {
int src;
int dst;
char name[10];
int t1;
int t2;
int age;
int sex;
int mobile;
}
struct record_s record[2] = {
{1, 2, "jack", 5, 6, 50, 1, 1234567890},
{3, 4, "john", 7, 8, 60, 2, 1122334455}
};
table.insert(record[0]);
table.insert(record[1]);
/* search using key1 */
struct key1_s key1;
key1.src = 1;
key1.dst = 2;
strncpy(key1.name, "jack", 10);
key1.t1 = 5;
key1.t2 = 6;
table.find(key1); // should return pointer to record[0]
/* search using key2 */
struct key2_s key2;
key2.src = 1;
key2.dst = 2;
strncpy(key1.name, "jack", 10);
table.find(key2); // should return pointer to record[0]
/* search using key3 */
struct key3_s key3;
key3.src = 1;
key3.dst = 2;
key3.t1 = 5;
table.find(key3); // should return pointer to record[0]
찾기()가 성공적으로 포인터를 돌려주는 경우, 나는 나이, 성별, 모바일과 같은 레코드의 필드를 업데이트하고 싶습니다.
표기법으로 혼란을 SRY, 나는이 문제에 대한 BMI를 사용했던 일부 의사 코드 – Athif