DB Internat Operation (2)

DB 10-2

파일의 조직방법

1 순차방법 (시퀀셜 메소드) : 물리적 저장순서를 논리적 순서와 같게 저장하는 방법.

2 인덱스방법 : 인덱스를 찾아가 해당 주소의 레코드를 접근하는 방법

멀티레벨인덱스는 트리 형식이다. 

B트리 : m웨이 검색 트리

루트와 리프 노드를 제외하고, 서브트리의 내부 노드는 적어도 차수/2 이다. 적어도 키의 수는 차수/2-1 이다.

루트가 리프가 아니라면 적어도 2개의 서브트리를 가진다.

리프노드들은 같은 레벨이다.

삽입시, 빈공간이 없으면, 두개로 쪼개고,

가운데 거가 위로 올라감.

삭제시, 오른쪽 자식노드에서 가장 작은값과 자신을 바꾸고,

날림.

왼쪽자식노드에서 삭제후 모두 빌 때, 2개인 곳에서 하나를 땡겨옴. 땡겨올때, 앞에서 순차로 확인해 댕겨온다.

모두다 가난할 땐, 머지를 하는데,

제일 가난한 노드와 그 오른쪽노드를 합침.

합치면서 부모노드의 내용도 빼온다.

'

B+트리 : B트리는 전체 트리가 실제 값인데 반해, B+트리는 인덱스 세트부분과 리프노드로 구성된 순차세트가 있다.

삽입은 B트리와 비슷한데, 인덱스 노드 수정 후,

리프노드에도 그 값이 있어야한다.

삭제시, 리프노드의값만 지우고 인덱스노드의 값은 그대로.

삭제시, 한쪽 리프노드의 값이 언더플로우 발생시,

값을 당겨옴. 부모노드의 값은, 왼쪽자식의 가장큰값과 같거나 크다. 오른쪽자식의 가장 작은 값보다는 작다.

머지 시에, 합쳐지면서 부모노드의 인덱스노드의 값은 지움.