B-트리에서 키를 삭제하는 것은 삽입 연산과 유사하지만, 더 복잡하다.삭제는 모든 노드에서 가능하지만, 리프(leaf) 노드가 아니라 내부(internal) 노드에서 삭제 연산을 수행한다면 삭제 시 내부 노드의 자식들을 재정렬해야 한다. 이런 상황을 해결하기 위해, 모든 삭제 연산을 리프 노드에서 수행하도록 한다. 내부 노드에 있는 삭제할 키를 리프 노드로 이동한다.이동 후 내부 노드에서 해당 키를 삭제한다.만약 이 과정에서 B-트리의 속성이 위배되면, 트리 구조를 재정비(fixup) 해야 한다. Case 1: 삭제할 키가 리프 노드에 존재하는 경우 즉, 삭제할 노드가 (t-1)보다 많은 자식 노드를 가지고 있는 경우이때는 노드에 최소 키 수를 유지하는 조건(B-트리 속성)이 위배되지 않는다..
B-TREE-SEARCH(x, k): i = 1 while i ≤ x.n and k > x.key_i: i = i + 1 if i ≤ x.n and k == x.key_i: return (x, i) elif x.leaf: return NIL else: DISK-READ(x.c_i) return B-TREE-SEARCH(x.c_i, k) B-트리는 여러 키와 자식을 포함할 수 있으므로 탐색 절차가 이진 트리보다 복잡하다.위 알고리즘은 트리 구조에서 서브트리를 탐색할 수 있도록 일반화된 형태로 설계한 것이다. 위 설계의 입력부분인 x는 탐색을 시작할 서브트리의 루트 노드를 가리키는 포인터를 의미하고, k는 탐색하고자..
디스크 소개 디스크는 플래터(platter)와 스핀들(spindle)로 구성되어 있으며, 헤드(head)가 데이터를 읽고 쓴다.디스크에서 데이터를 읽기 위해서는플래터가 회전해서 해당 데이터에 접근하고,헤드가 중심에서 가장자리로 이동해서 정확한 트랙에 도달하면 원하는 데이터를 읽는다. 그런데 이런 기계적인 움직임 때문에 디스크 접근은 매우 느리다. 게다가 현실세계에서는 점점더 메모리 요구량이 커지고 있다.큰 용량의 데이터를 저장하려면 디스크와 같은 보조 저장 장치에 저장해야하는데,기계적인 움직임으로 인해 보조 저장 장치에 저장된 데이터에 접근하는 속도는 메인 메모리보다 느리다. 비록 보조 저장 장치는 용량이 크지만 메모리보다 느리기 때문에, 효율적인 디스크 I/O가 중요하다.그래서 이를 위한 해결..
1. 데이터 추상화와 데이터 모델 데이터 추상화데이터 추상화는 데이터를 관리할 때 사용자가 복잡한 물리적 세부 사항을 몰라도 되게 만드는 과정이다. 사용자는 데이터의 핵심 정보만 볼 수 있고, 데이터가 컴퓨터에 어떻게 저장되는지는 숨겨진다. 데이터 추상화의 주요 개념:억제(Suppression):데이터가 물리적으로 어떻게 저장되는지(디스크에 파일이 어떻게 배치되는지 등) 사용자는 알 필요가 없다.강조(Highlighting):사용자가 데이터를 이해하는 데 필요한 핵심 정보만 노출한다. 예를 들어, 사용자는 학생의 이름과 학번만 볼 수 있고, 저장 위치나 세부 구조는 신경 쓰지 않아도 된다.사용자 맞춤 뷰 제공:각 사용자가 자신의 필요에 맞게 데이터를 볼 수 있다. 예를 들어, 재무팀은 결제 정보만 보..
데이터베이스(DB)는 논리적으로 일관된 관련 데이터들의 모음을 말한다.이것은 사용자가 데이터베이스를 쉽게 생성하고 유지할 수 있도록 데이터베이스 관리 시스템(DBMS)에 의해 관리되고,DBMS를 이용하여 데이터베이스를 정의, 구축, 조작, 공유할 수 있다. 데이터베이스의 특징 자기 기술적인 특성(Self-describing nature)프로그램과 데이터 간의 독립성 및 데이터 추상화다중 데이터 뷰 지원데이터 공유 및 다중 사용자 트랜잭션 처리 자기 기술적인 특징데이터베이스 시스템은 데이터베이스 자체뿐만 아니라 구조를 설명하는 메타데이터도 포함하고 있다. 이를 통해 데이터 베이스를 유지하고 관리할 수 있다.메타데이터: 데이터베이스 구조와 제약 조건을 정의하는 정보로, 데이터베이스를 유지하는..