RDB의 INDEX를 B-Tree 구조로 가져가면 좋은 이유에 대해 궁금증이 있습니다.

Question

RDB의 Index를 B-Tree 구조로 하면 삽입, 수정, 삭제 시 O(logN)의 시간복잡도를 갖는다고 하셨는데 어떻게 그렇게 되는지 궁금합니다.

개발남노씨 · Answer

B-Tree 구조의 검색(lookup)은 O(logN)입니다. BST와 비슷하다고 보시면 돼요! 그럼 B-Tree의 삽입(Insert), 삭제(Delete), 수정(Update)은 어떤 과정으로 진행되는지 좀 더 설명드릴게요! 일단 수정(Update)는 삭제 후 삽입한다고 생각하시면 됩니다. 따라서 삽입과 삭제의 과정만 아시면 됩니다. 그리고 기본적으로 삽입과 삭제는 검색과 동일한 알고리즘으로 진행되지만 복잡한 과정이 추가 됩니다. 그것은 leaf node를 분할하거나 합치는 과정 입니다. - 삽입: 검색(lookup)과 동일한 과정으로 삽입할 search-key가 저장되어 있을 leaf node를 찾습니다. 이과정에서 O(logN)이 걸리겠죠. 그리고 데이터를 삽입하는데, leaf node가 너무 많은 데이터를 저장하고 있다면 분할합니다. - 삭제: 검색(lookup)과 동일한 과정으로 삽입할 search-key가 저장되어 있을 leaf node를 찾습니다. 이과정에서 O(logN)이 걸리겠죠. 그리고 데이터를 삭제하는데, leaf node가 너무 적은 데이터를 저장하고 있다면 옆 leaf node와 합칩니다. leaf node를 합치고 분할한다는 말 한마디로 축약했는데, 이 과정이 꽤나 복잡합니다. 하지만 면접강의에서 다루기에는 너무 깊은 내용이라 링크를 하나 남겨드릴게요!! 더 자세한 내용이 궁금하시면 참고해 주세요 :) B-Tree insertion B-Tree Delete