개요
데이터를 효과적으로 다루기 위해서는 많은 데이터 구조에 대해 알아놓아야 한다.
오늘은 생소한 데이터 구조들 Trie, B-Tree, Priority Queue에 관해 다룰 것이다.
Trie
이는 문자열 검색과 같은 상황에서 유용하게 사용하는 데이터 구조입니다.
아래 유튜브 영상이 굉장히 자세히 설명하고 있습니다.
B-Tree
B tree는 개념이 간단하지만, insert, delete과 관련된 부분이 복잡하다.
아래 유튜브 영상이 잘 설명하고 있다.
B+ Tree
B+ Tree의 경우, B Tree와 구조적으로 유사하지만, data에 대한 포인터를 leaf node에만 저장한다는 특징이 있다. 그리고 leaf-node는 linked-list을 구성하고 있기 때문에, 범위 탐색에 수월하다는 장점이 있다.
삽입의 경우, leaf node에만 삽입을 하면 된다. 만약 leaf node가 overflow가 일어나면, 이를 쪼개고 key한개를 parent node에 복사하면 된다.(B-Tree와 동일하다)
삭제의 경우, key값이 leaf node의 맨 앞에 존재하지 않는 경우 이는 internal node에 key가 사용되지 않는다는 의미이므로 그냥 삭제하면 된다.
하지만, key 값이 leaf node의 맨 앞에 존재할 경우, leaf node상에서 다음 key 값으로 대체하면 된다.
B+ Tree는 file system에 사용될 수 있는데, 각 node들이 disk에 저장되어있다고 할 때 sequential read을 하려고 한다면 leaf node에 있는 linked list 구조를 iterate 하면 되기 때문이다. 매번 inode의 주소를 찾기 위해 tree를 traverse할 필요가 없다.
더 나아가 B+ Tree는 DB Index 구조에도 사용된다.
한가지 더 신기한 점을 말하자면, 멀티 쓰레딩 프로그램에 사용되는 Concurrent Hashtable이 B+ Tree와 유사한 구조를 지니고 있다.
