child prefixes 관리 구조 개선 - skip list 사용 #562
Description
child prefixes 관리 구조를 개선한다.
기존 구조
- prefix hash table에 child prefixes도 함께 연결하여 관리하고 있다.
- 이로 인한 이슈는
- 최상위 prefix 탐색 시 child prefixes 포함하여 탐색하게 되므로 탐색 비용이 커지며,
탐색 시에 child prefixes를 제외하는 로직을 가져야 한다. - 최상위 prefix 제거 시에 child prefixes도 함께 제거해야 한다.
이 경우, prefix hash table의 모든 prefixes를 탐색해야 하는 부담이 있다. - 많은 수의 child prefixes가 생성되면, prefix hash table 탐색 비용이 커지며,
prefix hash table 확장이 고려되어야 한다.
- 최상위 prefix 탐색 시 child prefixes 포함하여 탐색하게 되므로 탐색 비용이 커지며,
개선 구조
- prefix hash table에는 최상위 prefixes 들만 연결하여 관리한다.
- 최상위 prefix에 속하는 child prefixes들을 skip list로 관리하며, 최상위 prefix에서 skip list를 접근하도록 한다.
- 따라서,
- 최상위 prefix 탐색은 prefix hash table을 탐색하면 된다.
- 특정 최상위 prefix의 child prefixes는 그 prefix에 포함된 skip_list를 탐색하여 접근할 수 있다.
- 최상위 prefixes만 prefix hash table에 연결되므로, prefix hash table 확장을 고려하지 않아도 된다.
- 참고로, 특정 child prefix 조회는 prefix hash table 탐색 외에 skip list 탐색 부담이 있지만 무시할 만한 정도이다.