데이터베이스는 과연 어떤 자료 구조를 바탕으로 구현될까요? 📙 자료 구조 1️⃣ Skiplist 일반적인 인메모리(in-memory) 인덱스 타입으로 레디스(redis)에 사용된다. 2️⃣ Hash index 'Map' 또는 'Collection'을 사용한 가장 일반적인 구현 방법. 가장 보편적으로 이해하고 있는 자료 구조인 것 같아요. 3️⃣ SSTable 불변성 on-desk “Map” 사용. 4️⃣ LSM Tree 위 언급한 Skiplist와 SSTable을 합친 자료 구조이며 특히 write throughout에 최적화 된 자료 구조이다. 하지만 디스크 콤팩션이 데이터베이스 퍼포먼스에 영향을 미칠 수 있다. 📌 덧붙여서, 디스크 콤팩션(compaction)은 LSM-Tree을 이야기할 때 많이 언급됩니다. 절충점을 찾는 게 아직 어려운 숙제이기도 하고, 튜닝을 통해 극복 가능하나, 관련 주제를 이야기할 때 도움되므로 추가적으로 찾아서 한 번 읽어보세요. 5️⃣ B-Tree 디스크를 기반으로 한 구조이며 Consistent한 write과 read에 최적화 되어 있다. 그리고 데이터베이스를 구현할 때 가장 많이 사용되는 자료 구조이기도 하다. 📌 덧붙여서, B-Tree와 LSM-Tree는 요즘 데이터베이스를 이야기할 때 많이 언급됩니다. 각각 특정 속성에 최적화되어 있어서 비교해서 많이 언급되기도 하는데 관련글 찾아보고 한 번 읽어 보는 것도 좋을 것 같아요. 6️⃣ Suffix Tree 스트링 패턴 서치에 사용되며, 리트코드 문제에도 꽤 보이는 자료 구조 타입이다. 7️⃣ R-Tree Near neighbors와 같은 Multi-dimension 서치. 아래 사이트에서 자세하게 언급하지 않아요. 좀 더 깊게 파고들고 싶다면 아래 책 추천합니다. 📚책 추천 Dstabase Internals: Deep Dive Into How Distributed Data Systems Work - Alex Petrov 데이터베이스가 어떻게 구현되는지 자세하게 알고 싶다면 이 책 추천해요. 가볍게 읽기에는 주제가 무거운 책이라 집중해서 읽어야 합니다. LSM-Tree 등 어떻게 데이터가 분산되고 저장되는지, 평소 깊이 들여다보지 않았거나 궁금하신 분들은 한 번 꼭 읽어보는 것을 추천합니다. 출처: bytebytego.com 🪴 함께 읽으면 좋은 글: 코딩 테스트 실력 향상시키기: 니트코드 150 https://careerly.co.kr/comments/69725 개발자가 읽어야 할 책 20권 https://careerly.co.kr/comments/67611 [분산 시스템 공부법] 유튜브 채널 추천, 학습 효과 극대화 하기 https://careerly.co.kr/comments/67026 개발자가 꼭 봐야 할 책 - 데이터 중심 애플리케이션 설계 https://careerly.co.kr/comments/67004