본문 바로가기

전체 글

(185)
11. B+-tree 업데이트 내역 2023.12.23 B-Tree의 문제점 추가 B-Tree의 문제 시간 복잡도가 균등하지 않다. 노드에도 데이터가 있었기 때문에, logN이라도 상황에 따라선 더 빠를 수도, 늦을 수도 있다. 이러한 문제는 성능 측정 과정에서 모호한 결과를 주게 된다. 이 문제를 해결하기 위해 B+Tree에선 다음과 같이 적용했다. 모든 데이터는 리프 노드에 있다. 중간 노드는 키값만 저장한다. 인접한 노드 탐색이 어렵다. WHERE 절에 BETWEEN, IN 같이 범위 조건을 걸게 되면, 인접한 노드라도 부모 노드를 타고 올라가야 한다. 상황에 따라선, 루트 노드까지 올라갈 수도 있기 때문에 무척 비효율적이다. 예를 들면, 다음 트리에서 7 ~ 9를 찾고자 한다면 루트 노드까지 올라가야 한다. 이 문제를..
10. B-Tree 업데이트 내역 2023.12.23 노드, 시간 복잡도 및 삽입, 삭제에 알아둘 점 추가 여기서 B-Tree를 테스트해 볼 수 있다. http://www.cs.usfca.edu/~galles/visualization/BTree.html B-Tree Visualization www.cs.usfca.edu B-Tree 특성 여기서 노드는 RDBMS 기준 최소 단위인 block이라 보면 된다. root 노드가 leaf노드가 아닌 경우 최소 2개의 서브트리를 가진다 모든 리프 노드들은 같은 레벨을 가져야 함 node 내부의 키 값들은 오름차순이다. -> 키 내부에서도 어떤 키의 서브트리를 가야할지 결정해야 한다. 리프 노드들은 최소 (p/2 -1)개, 최대 (p-1)개의 키를 가져야 함 리프가 아닌 노드들은 서브..
9. Single Level ordered Index 업데이트 내역 2023.12.23 클러스터링, 논 클러스터링 설명 개선 레코드 검색 속도를 높이는데 사용. 3가지 유형이 있다. 1. Primary Index 2. Clustering Index 3. Secondary Index (보조키로 검색하는 방법) Primary Index 정렬된 Field에 대한 Index, 중복을 허용하지 않는다. 필드 구성은 다음과 같다. K : Ordering Key Field (PK) 정렬된 Key Feild. P : 디스크 블록 포인터 데이터 블록당 Index Entry는 1개 대표 레코드라 하고 Anchor Record라고도 한다. 작동 방식 P(i)가 가리키는 블록으로 접근해, 그 안에서 K(i)의 위치를 찾는다. PK가 없으면 어떻게 될까? 테이블에 PK가 존재하지..
8. RAID Redundant Arrays of Inexpensive Disks 혹은 Redundant Arrays of Independent Disks 라고 부른다. 저장장치의 신뢰성을 높이기 위한 방법으로, 여러 하드디스크에 일부 중복된 데이터를 나누어 저장하는 방식이다. mirroring 같은 데이터를 여러 하드디스크에 넣는 방법 striping 데이터를 분산시키는 방법 bit 단위로 분할할 수도 있고, block 단위로 분할할 수도 있다. RAID 0 데이터를 Block 단위로 번갈아 저장한다. RAID 1 다른 디스크에 똑같은 블록을 저장해, 신뢰성을 높인다 하지만 저장할 블록이 많을수록 비용이 크게 증가한다. RAID 2 striping 방식을 사용하고, 오류 검출을 위한 해밍코드 적용 최근 디스크 드라이..
7. File File이란? -> record의 연속 Fixed length record : 모든 레코드는 정확히 같은 사이즈 variable length record : 모든 레코드는 다른 사이즈 Primary File Organizations heap file(비정렬 파일) - 새로운 데이터가 생성되면 파일의 끝에 추가됨 sorted file(순차 파일) - 검색키를 기반으로 정렬된 순서를 갖음 hashed file - hash function을 적용해 디스크에서 record 위치 결정 블록 저장방식 블록 B byte를 R byte로 나눔 (B >= R) Blocking Factor (bfr) = B / R ex) 고정 길이 레코드에서 512byte의 file이 있고, record가 100byte일 때 bfr = ..
6. 정규화 FD (Functional Dependency) 함수적 종속성. relation R에서, attribute 집합 X와 Y가 있을 때 attribute X에 대해 Y가 오직 하나만 매칭되어야 함. 이 때, X를 결정자라 하고, Y를 종속자라 한다. 표기 : FD: X ->Y 만약, X의 어떤 부분집합도, Y를 결정하지 못하면 FFD (Full Functional Dependency)라고 한다. (2NF) 정규화 1NF relation R의 모든 도메인은 원자값(atomic value)를 가져야만 함. 각 row와 column은 값을 하나씩 가져야만 함. 만약, 집합이나 다수의 값으로 구성돼 있으면, 이걸 쪼개줘야 함. 예를 들어 다음 테이블 구조를 가진다 하자. Dname Dnumber Dmgr_ssn D..
5. ER 다이어그램 data model을 개념적으로 표현하기 위해 사용 Entity 이름, attribute로 표현 스키마에 해당함 직사각형으로 표현 Attributes entity의 요소들 Attribute는 서브 Attribute가질 수 있음. 밑줄이 쳐진 attribute는 key라고 한다. 만약, Key Attribute에 서브 Attribute 가 있다면, 그 키는 복합키가 된다. Relationship 원래는 Attribute에 다른 Entity를 연결하는 식(참조관계 속성)이었는데, 그 속성을 지우고 다음과 같이 마름모로 표현 attribute를 가질 수 있다. constraint Cardinality Ratios 1:1, 1:N, N:1, M:N 로 표현하고, 하나의 관계성에 참여할 수 있는 개체 수를 나타낸..
4. 관계 대수, 해석 구분 관계 대수 (Relational Algebra) 관계 해석 (Relational Calculus) 목적 어떻게? 무엇을? 절차 순차적 비순차적 관계 연산자 집합 연산자 연산자 기호 표현 의미 Union U R U S relation R과 S의 합집합 Interaction ∩ R ∩ S relation R과 S의 교집합 Difference ㅡ R ㅡ S relation R과 S의 차집합 Cartesian X R X S relation R과 S의 모든 원소들의 곱 관계 연산자 연산자 기호 표현 의미 Select σ σc(R) Relation R에서 조건 c를 만족하는 튜플 반환 교환 법칙 가능 Project π πL(R) Relation R에서 attributes의 집합 L로 구성된 튜플 반환 중복 허..