Programming/Data Structure 2

[Data Structure] B-tree 정의 및 장/단점

검색을 위한 자료구조 중에 잠재력이 가장 큰 것은 역시 트리이다. 그 중 이번 포스팅에서는 B-tree에 대해 알아볼 것이다. B-tree는 주로 데이터베이스에서 인덱스를 저장할 때, 많이 사용된다. 이번 포스팅을 찾은 사람 중에 인덱스 관련 글을 보던 중, B-tree에 대해 궁금해져 찾아온 사람도 있을 것이다. 그럼 B-tree에 대해 알아보자. B-tree의 정의- 모든 노드는 최대 m개의 자식들을 가진다.- 루트노드와 리프노드가 아닌 모든노드는 최소 m/2개의 자식을 가진다.- 루트노드는 최소 2개 이상의 자식을 가진다.- k개의 자식을 가진 리프노드가 아닌 노드는 k-1개의 키를 가진다.- 모든 리프노드들은 같은 높이에 있어야 한다.- 모든 노드들은 키와 자식노드에 대한 포인터로 이루어져 있다...

[Data Structure] 자료구조 (Data Structure)

자료구조 : 데이터들의 관계를 구조화한 것 자료구조의 분류선형 자료구조 : 리스트, 스택, 큐비선형 자료구조 : 트리, 그래프 ●배열(Array)-타입이 동일한 데이터들의 집합-연속된 공간의 메모리를 할당-인덱스를 통하여 자료의 순서와 위치를 표시-인덱스를 이용하여 직접적으로 자료에 접근 가능 ●리스트(List)-특정원소의 탐색-머리(Head)부터 꼬리(Tail)까지 순차탐색-i번째 원소의 삽입, 삭제 배열리스트(Array List)탐색 : 머리(Head)부터 순차탐색 가능, 인덱스를 이용한 직접 접근 가능 삽입 : 끝에 삽입하면 해당 메모리 주소에 삽입, 중간에 삽입하면 이후의 모든 데이터를 뒤로 밀고 삽입 삭제 : 끝에 있는 자료는 바로 삭제, 중간에 있는 데이터는 삭제 후에 이후의 데이터를 모두 당..