나만의 공부 노트

ISAM(Indexed Sequential Access Method) - 정적 인덱스 - 데이터 삽입이 빈번할 경우, 오버플로우 페이지를 sequential하게 연결하기 때문에 logN의 시간복잡도가 무의미해진다. 동적 인덱스 - 가장 처음 고안된 알고리즘 : AVL tree(height의 차이를 최소화) - AVL tree를 사용하지 않는 이유 : 수많은 rotation으로 인해, i/o가 많아짐 - RB tree vs B+ tree - RB tree : 밸런싱을 위한 rotation 작업을 모아서 한 번에 처리하는 알고리즘 - B+ tree : 탐색할 수 있는 자식 노드를 2개 이상으로 늘리는 알고리즘 B+ tree - ISAM과 비슷한 구조 - interior node = / leaf node = ..

파일 안의 page를 어떻게 구성할 것인지에 관해서 * Heap Files에서는 API : recordID(pageID, slotID)를 통해 레코드 아이디를 가져온다. 즉, 쿼리 단계에서 record를 가져오려면 page와 slot이 필요하다. -> 그러나 key를 이용해서 record를 찾는다면, page와 slot이 꼭 필요하지 않을 수 있지 않을까? = index * Cost Model B : data blocks R : records per block D : delay time Tree Indexes - page Id, slot으로 record id를 찾는 것이 아닌, key 값을 통해 record Id를 찾는 방법 - Data Entries에 key와 recordID를 pair로 저장하므로써,..

Architecture of a DBMS SQL을 처리하기 위한 DBMS의 구조 = 계층화(Layer)를 통해 구현(유지보수 용이) -> 데이터베이스 전문가들은 이러한 os, system을 이용하지 않고, 물리 장치의 구조를 파악한 뒤 직접 기록한다고 함(시스템을 이용하면 오버헤드가 발생하기 때문) 1. Query Parsing & Optimization 엄밀히 따지면 컴파일은 아니나, human friendly하게 쓰인 sql을 기계어로 번역하는 과정 parsing -> syntax check -> Relational Operator & Optimization(여러 query plan 중 가장 짧게 걸릴 것 같은 query plan을 추측하여 선택) 2. Relational Operators Optim..

Database Engines - ranking DB vs DBMS DB : Database -> data를 schema로 구조화한 것 DBMS : Database Management System -> database를 관리하는 시스템(logical/physical data independence) ACID Atomicity : 여러 개의 작업을 하나의 단위로 구성 Consistency : 일관된 데이터 구조(logging) Isolation : 각 트랜잭션은 serial하게 작업된 결과와 동일하게 concurrent로 작업(locking) Durability : commit이 되었다면 데이터베이스에 저장이 되어야한다. SQL = Structured Query Language DDL = Data Defi..