컴퓨터/데이터베이스9 [CMU 15-445 Intro to DB Sys] Lec09 Index Concurrency Concurrency Control to ensure "correct" results for concurrent operations on a shared object logical correctness: 읽어야 하는 값을 잘 읽어온다는 의미 physical correctness: object의 internal representation이 제대로 되어 있다는 의미 Locks vs. Latches Locks(Transactions): high-level에서 db의 Logical contents를 다른 transaction들로부터 보호함. deadlock이 생기면 rollback할 수 있어야 함. latches(workers): low-level에서 DBMS의 internal data structure가 있는.. 2024. 1. 9. [CMU 15-445 Intro to DB Sys] Lec08 B+Tree Index B+Tree self-balancing, ordered tree data structure search, sequential access, insertion, deletions을 $O(\log n)$에 수행 $M$-way search tree($M$: maximum number of children a node can have) perfectly balanced(every leaf node is at the same depth) every node other than the root is at least half-full($M/2 -1 \leq # keys \leq M - 1$) every inner node with $k$ keys has $k+1$ non null children B-Tree와의 차이.. 2024. 1. 5. [CMU 15-445 Intro to DB Sys] Lec07 Hash Tables DBMS에 사용되는 자료구조의 디자인에 있어서는 data organization(어떻게 효율적으로 access할 수 있을지), concurrency(여러 Thread가 문제 없이 access할 수 있도록)를 고려해야 함. Hash Tables unordered associative array that maps keys to values로서, 해쉬함수를 통해 key로부터 value가 담긴 곳의 offset을 계산한다. space complexity는 $O(n)$, time complexity는 평균적으로 $O(1)$, 최악의 경우 $O(n)$다. 그럼에도 불구하고 DBMS에서는 $O(1)$과 같은 constant도 최적화하는 것이 중요하다.Hash Function 해쉬함수는 large key space에서.. 2024. 1. 4. [CMU 15-445 Intro to DB Sys] Lec06 Memory & Disk IO spatial하게는 함께 사용되는 페이지들을 디스크에서 물리적으로 가깝게 유지하고 싶으며, temporal하게는 디스크에서 읽어올 때 발생하는 stall의 횟수를 최소화하는 것이다. Buffer Pool buffer pool은 디스크로부터 읽어온 페이지들을 보관하는 in-memory cache로서, 커다란 메모리 구역임. 이는 array of fixed-size pages로 구성되어 있음. 개별 entry를 Frame이라고 부름. DBMS에서 특정 페이지를 요청하게 되면 exact copy가 frame에 옮겨짐. dirty page는 buffer된 채로 있으며, 즉시 쓰여지지 않음. page table: 현재 메모리 상에 있는 페이지들의 현황을 관리함. 주로 fixed-size hash table이 사용.. 2024. 1. 4. 이전 1 2 3 다음