우당탕탕 공부중

드디어 B+ Tree까지 왔다. 이제 이것만 하면 코딩 시작...!!!! 빨리 이해해야지 .. 후...  B+ Tree는 B Tree의 변형된 버전으로 데이터베이스 인덱스 구조에서 매우 많이 사용되는 자료 구조이다. B Tree와 유사하지만 몇가지 차이점이 있어서 대용량 데이터 검색에 최적화된 특성을 가지고 있다. B+ Tree는 균형 다진 트리(Balanced Multiway Tree)로 B Tree와 마찬가지로 데이터를 효율적으로 관리하고 검색하기 위한 트리 구조이다. 하지만 B Tree와 달리 모든 실제 데이터는 리프 노드에만 저장되고 내부 노드는 오직 인덱스 역할만 한다. B+ Tree의 구조 및 특징· 리프 노드실제 데이터를 저장하고 각 리프 노드에는 다음 리프 노드로의 포인터가 존재한다. 이를..

이진트리에 대해 알아보았으니 이제 균형 이진 탐색 트리의 한 종류인 B Tree에 대해 공부해 보도록 하겠다. B Tree는 데이터 베이스와 파일 시스템에서 사용되는 트리 구조이다. DB에 트리 구조가 사용된다는 생각을 해본적이 없어서 선배들이 데베시에서 과제 B+ Tree 구현이 정말 어렵다고 했을 때 자료구조에 나오는 걸 DB에서 과제로 나오는거지 했었던 기억이 있다. 그 이유의 즉슨! DB에 B Tree, B+ Tree가 쓰이기 때문이다! 앞서 공부했든 이진 탐색 트리의 일반화를 통해 만들어졌다. B Tree는 노드가 2개 이상의 자식을 가질 수 있어 트리의 높이를 낮게 유지하고 디스크 I/O를 최소화할 수 있다. 또한 하나의 노드에 많은 수의 정보를 담을 수 있어서 높이를 낮게 유지하는데 도움이 ..

B+ Tree를 구현하라는 과제가 나왔다. 우리학교 데베시는 상당한 난도를 자랑한다. 자료구조를 2-1때 배웠기 때문에 당장 B Tree도 기억이 나지 않는 상황 ...! 과제를 하지 못하면 가장 코어 과목을 드랍해야하는 상황에 놓이기 때문에 빠르게 트리 구조를 복습해보기로 하였다. B-Tree를 시작하기 전 이진트리 개념부터 공부하고 넘어가자. 이진트리 종류는 생각보다 다양하다. 그 종류들을 정리해 보도록 하겠다. 1. 이진트리(Binary Tree)트리 중에서 각 노드가 최대 2개의 자식을 가지는 트리이다. 이 두 자식 노드를 왼쪽 자식(Left Child)과 오른쪽 자식(Right Child)이라 부른다. 같은 루트에 같은 자식 노드를 하나 가지고 있더라도 왼쪽과 오른쪽 놓인 위치에 따라 다른 자식..