indexing4 [Query Processing]Sorting mainmemory에 올려서 정렬할 수 있는 것을 internal sort external sort의 경우는 disk의 table을 main memory에 올릴 수 있는 크기로 나누어서 internal sort를 하고 file로 저장한다. 이렇게 저장된 것을 run이라고 하며 run들을 merge를 하게 되면 특정한 칼럼에 대해 정렬할 수 있다. external sort-merge main memory 크기는 M개의 page가 존재할 수 있음. page=block이라고 본다. 1.m개의 block을 읽어서 2.소팅한 후 3.run을 저장한다. 4.n 개의 run이 주어졌을 때 merge한다. 1~4의 결과 다음과 같은 결과가 된다. run1(multiple page) run2 run3 ... runN N.. 2020. 6. 7. [Indexing]Bitmap Index m개의 레코드가 있으면 n개의 비트를 할당하는 방식이다. 특정한 칼럼, 예를 들면 학년(1~4)을 가지고 구분을 하면 4개의 집합으로 나뉜다. 1학년인지 파악하는 bitmap을 하나 만들 수 있다. 1학년, 3학년, 1학년, 1학년, 2학년 의 레코드가 있다고하면 10110과 같은 값을 가지게 한다. 2학년인지 파악하는 bitmap을 만들면 00001이 된다. 3학년: 01000 4학년: 00000 bitmap index는 칼럼의 값이 몇 개만 존재할 때 만들 수 있다. 위와 같은 학년이라던지 성별과 같은 칼럼에 대해서 가능하다. 학생의 학점과 같은 경우에도 가능하다. 범위에 대한 bitmap을 만들 수 있다. 4.0이상, 3.0이상 4.0 미만 과 같은 방식으로 만들 수도 있다. bitmap index.. 2020. 6. 6. [Indexing]B+ tree index simple index 사이즈가 커지게 되면 메인 메모리에 올리기 어려워서 비효율적이다. 그렇기 떄문에 b+ tree나 hashing을 쓰게 된다. 학생 테이블이 있을 때 학번에 대해서 검색이 자주 일어나면 미리 학번에 대한 b+ tree를 disk에 만들어두고 사용할 수 있다. 이에 대한 hash file을 만들어 두어도 된다. B tree family = B tree, B+ tree, B* tree 가장 장점이 많은 트리가 B+ tree이고 가장 널리 사용된다. insert, delete 될 때 변화가 지역적으로 발생하는 것이 장점이다. simple index의 장점은 메인 메모리에 로드해서 사용할 수 있는데 크기가 커지면 그 비용이 커진다. 따라서 B+ tree가 대안이 될 수 있다. B+ tree.. 2020. 6. 5. [Indexing]Overview search에 대한 효율적인 처리를 위해서 search를 위한 tool이 필요하다. dbms search--> search tool --->file subtopics basic concept simple index b+ tree index b+ tree variations static hashing dynamic hashing bitmap index basic concept indexing: key가 있고 그 조건을 만족시키는 정보를 찾아낼 때 indexing을 통해 속도를 높인다. 대표적인 것이 책의 index 부분이다. 책 뒤에 있는 색인 부분이 simple index이다. 구조이다. 두 가지 index ordered indices hash indices evaluation metric -access.. 2020. 6. 5. 이전 1 다음
