indexes

지난 주제 다루기 전에 우리 해시 테이블에 대해서 공부했었는데 해시 테이블의 특징은 굉장히 빠른 검색 속도를 지니고 있습니다. 그런데 내부적으로만 사용하고 테이블의 인덱스, 세진으로는 사용하지 않았는데 그 이유가 레인지 스캔이 불가능이라고 했습니다. 레인지 스캔이 불가능합니다. 예를 들어서 연봉이 2천만원부터 8천만원 사이에 있는 모든 사원들을 알려보라고 했을 때

tc 테이블은 정확하게 2500이면 2500, 2600, 2600 이렇게 정확하게 찾아오는데 범위가 주어진 상태에서 갖고 오라고 하면 그걸 할 수가 없어요. 그래서 테이블 인덱스로는 사용하지는 않습니다. 물론 정확한 e-exec트 매칭을 필요로 하는 인덱스에서는 사용할 수 있습니다. 굉장히 고성능의 e-exec트 매칭의 용도로 인덱싱을 해야 된다. 그랬을 때는 사용할 수 있는데 일반적으로는 사용하지 않는다. 라고 말씀드렸었고요.

그래서 b+tree를 쓸건데, b+tree는 특징이 디스크에 존재하기 때문에 n개의 갈릇길이 있습니다. n개의 갈릇길이 있는 이유가, 킷값을 여러개 갖고 있어서 원래 키값이 최대 3개 갖고 있을 수 있다고 하면 갈릇길이 1,2,3,4,4까지 존재하겠죠. b+tree는 굉장히 많은 아이템들이 있는데, 그 이유는 우리가 디스크에 존재하기 때문에 디스크에 한번 가서 읽어올 때 페이지 단위로 읽어온다고 했어요. 페이지가 보통 3KB만 된다고 했는데,

한 번 읽어올 때 4KB, 6KB를 읽어오기 때문에 최대한 페이지 크기에 맞춰서 제작을 하면 효율적으로 무항을 읽어올 수 있습니다. Bifurge 3의 특징이 키가 열기가 있다.

적어도 절반 정도 차이 있다.

루트는 절반 이상 안 차있어도 됩니다. 루트를 제외하고는 나머지는 절반 이상 차있어야 되는데 물론 절반 이상 차있지 않게 만들 수도 있어요. 절반 이상 차있지 않게 만들 수도 있는데 절반 이상 차게 만들어서 우리가 유지하면 좋은 점이 뭐가 있을까요? 하필이면 하나씩 있어도 되는데 왜 절반 이상 차게끔 그렇게 제약식으로 걸어두었을까? 여보세요. 생각을 해볼 수가 있는데 왜 절반 이상 차있어야 될까요?

어떤 쪽이 좋길래 절반 이상 차 있어야 될까요? 대표 37학생 계신가요? 네. 절반 이상 차 있어야 될 것 같아요. '블리키리스'가 많아요. 'S'가... 네. 맞습니다. 정확하게 말씀하셨는데 이게 우리가 트리의 깊이가 깊어지면 깊어질수록 디스크를 많이 읽어야 돼요. 맨 처음에 예를 들어서 내가 3번 키를 찾고 있다고 했을 때 루트에 시작하죠. 루트 시작할 때 디스크를 한번 읽어요. 그리고 20보다 작은 가급이 와야 돼서 그 디스크를 한번 읽고 그 시리보다 작은 디스크를 한번 읽고 이런 식으로 우리가 한 층 한 층 내려갈 때마다 디스크 굉장히 늙이죠. 디스크를 그 늙은 디스크를 한번씩 한번씩 읽어와야 되는데

아까 성취학생이 말씀하신 대로 여기 많이 키가 들어가 있어야지 값이 짧아지지 하나씩 있고 그러다 보면

이런 식으로 굉장히 깊어질 수 있거든요. 디스크 한 번 읽고 또 읽고 또 읽고 또 읽고 이런 식으로 디스크를 많이 읽게 돼요. 그래도 이루어지기 때문에 절반 이상 차이서 해야 된다. 그 제약 조건을 걸어놓은 것입니다. 그리고 이제 완벽하게 밸런스가 맞춰져 있다. 이것도 이건 성능의 안정성을 위해서 그런 것인데 바이널 서치트리처럼 어떨 때는 짧고 짧고 이렇게 확인해보면 우리가 어떤 무언가를 읽어올 때 시간이 얼마나 걸리는지 가늠이 안 되겠죠.

20이 읽을 때는 금방 읽고, 1번 읽을 때는 오래 걸리고 이런 식으로 편차가 생기게 되니까 예측이 불가능한데 이렇게 덱스가 다 맞춰져 있으면 어느정도 안정적으로 우리가 아이템을 끊어온는데 걸리는 습관을 예측할 수가 있어서 완벽하게 밸런스를 맞춰놨습니다. 그래서 집어넣을 때랑 뺄 때 다 한번씩 살펴봤었고 그리고 리프 노드에만 이제

value 값이 들어간다고 되어 있는데 b+3는 리프 노드에만 맨 마지막 장면에만 value가 있습니다. 그래서 학번으로 만들어진 인덱스였다고 하면 학번을 통해서 우리가 어떤 학생의 값을 읽어야겠죠. 중간중간에는 이 인터넷 노드에는 어떤 학번에 학생에 대한 정보가 들어있지 않고 맨 마지막 리프 노드까지 와야지 거기에 이제 정보가 들어있는데 실제로 밸류, 실제로 학생의 값이 적혀 있을 수도 있고요.

아니면 포인터가 있을 수도 있어요. 정보가 너무 커서 여기 다 저장하기 힘들다 라고 하면 어디에 가면 학생의 정보를 찾을 수 있어라고 하는 포인터도 이렇게 포인터로 바꿀 수도 있고요. 그리고 if node에서는 이렇게 sibling 포인터가 있어서 다음 단계, 다음 단계 이렇게 혹은 역방향으로 가게끔 만들어주는 포인터도 있어요. 그래서 내가 풀 스캔을 하고 싶다 라고 하면 바로 와서 한번 쭉 읽어보면 되겠대요.

그래서 이런 포인터들, 씨블링 포인터 이런 식으로 만들어진다고 말씀드렸었고요. 리프 노드에 실제로 값을 저장하는 방법이 두 번째 방법이고 첫 번째 방법은 포인터를 누른 것입니다. 그래서 어느 페이지에 어느 몇 번째 투플을 보면 거기에 넣어놓은 방법이 있어라고 하는 레코드 아이디를 우리가 반려값에 몇 번 사용하는 것일 수도 있고요.

실제로 실제값을 저장할 수도 있습니다. 그것이 기본키로 만들어진 인덱스였다 라고 하면 실제 내용이 들어와 있는데 주키가 아니라 다른 키로 만들어진 보조인덱스였다 라고 한다면 거기에 중국에서 원래 투플의 내용을 저장하게 되면 저장하는 것만 남겨서 팀에서 댓글 대신에 주키를 저장한다고 되어 있습니다. 그래서 보조키를 한 번 셔칭하면 주키가 나오는데 그 주키를 가지고 다시 여기로 들어와서 또 다시 검색을 해야 되는 뜻입니다.

이게 잘 이해가 안가실 수도 있을 것 같은데요. 다시 설명을 드리면은 학생 딜레이션이고요. 거의 학번이 죽기겠죠. 학번을 통해서 검색이 가능한 b+3백션입니다. 이런 식으로. 밑에 단에 내려오면은 그 학생의 정보가 다 들어있습니다. 어떤 학번은 이름이 뭐고 주소가 어디고 수강시 얼마고 이런 식으로

실제 변류가 다 적혀있는데, 그 대신에 이름으로 인덱스를 만들었다고 해봐요. 그러면 맨 마지막 단에 내려왔을 때, 이름에 따른 그 사람의 정보가 다 들어있는 게 아니라 이름하고 학번이 들어있어요. 그래서 이름으로 검색이 들어왔을 때에는 인덱스를 통해서 막 찾아 넣은 다음에 그 이름은 무슨 학번이야 라는 것을 알고 나서 다시 학번으로 돌아와서 진짜로 찾는다는 뜻입니다.

학번이 들어왔을 때에는 이 인재서를 통해서 빠르게 그 정보를 얻어오고 이름이 왔을 때는 이름을 통해서 학번을 얻어온 다음에 그 학번에 해당하는 자료들을 가져오는 형태로 되어 있어요. 그래서 주키일 때랑 주키가 아닐 때의 차이점이 있고요. b+3는 리프 노드에만 값을 받아야 합니다. 삽입할 때 스프릿이 하나씩 있고 그 다음에 지울 때 면즈이 하나씩 있고

- I'm sorry, I'm sorry.

여기서부터 하면 됩니다. 그 다음에 복합 인덱스에서 나와 있는데요. 복합 인덱스는 킷값을 열어볼까요?

이름과 그 다음에 학과와 그리고 뭐가 좋았던 거 이름, 학과

수강점이라고 할 거예요. 수강점이라고 할 수 있습니다. 이렇게 세 가지를 통해서 어떤 자료를 빠르게 얻어오는 데 도움이 되는 것을 만들 수가 있는데 인덱스 만드는 문법이 이렇게 되어 있습니다. 이렇게 한 다음에 키워드죠. 인덱스 이름 그 다음에 어느 릴레이션에서 a, c라는 업그레이드 으로 인덱스를 만들겠다 하는 것인데 a는 오른차순, a는 오른차순, c는 오른차순, c는

널값을 앞으로 보내보겠습니다. 인덱스 만들 때

널값이 맨 앞에 오거나 맨 뒤에 올 수 있다고 했었죠. 여기 지금 널값이 없는데 널값이 있다고 하면 맨 앞으로 보낼 수도 있고 맨 뒤로 보낼 수도 있습니다. 아까 인덱셀 만들 때 너를 앞으로 보내겠다고 하는 것이고요.

그리고는 정렬을 어떻게 할 것인지, 오른자손 할 것인지, 내륜자손 할 것인지, 그리고 널값을 앞으로 보낼 것인지, 뒤로 보낼 것인지 이렇게 할 수가 있고요. 빅플러스 트리 인덱스는 복합키의 프리픽스, 그러니까 앞의 것들만 사용할 수 있다고 되었는데, 무슨 뜻인가 하면, 이 abc를 다 쓰거나, 혹은 abc나 쓰거나, 혹은 ac나 쓰거나, 이렇게 앞의 부분들은 우리가 쓸 수가 있는데,

뒤에 부분, D로만 구성되어 있거나 C로만 구성되어 있는 것들은 대부분 지원하지 않는다 라고 되어 있는데요. 예제를 통해서 보시면, 이 분야가 좋습니다. 간혹가다 이것들도 지원하는 경우도 있습니다. 킷스캔이라고 하는데, 예제를 통해서 한번 보고 설명을 드릴게요. 지금 복합시 로 구성되어 있어요. 첫번째 어트리뷰트와 두번째 어트리뷰트 이렇게 했는데, 여기 보시면

1, 3, 2, 3, 3 이렇게 해볼까요?

앞에 게 작으면 1,3과 2를 봤을 때, 1,3이 앞에 오는 이유는 앞에 게 우선치 되어있습니다. 앞에 게 더 작죠. 그 다음에 1,3이 앞에 오고요. 그 다음에 2가 뒤로 오고 3,3이 뒤로 오고 이렇게 되어있는데 1,2를 찾겠다는 신호가 들어왔어요. 그럼 1,2는 어디로 가야 될까? 1,3보다 1,2가 앞에 있잖아요. 그래서 앞에 있기 때문에 이리 와서 읽어서 하나씩 찾아보니까 이 것만이 가지고 있었죠. 이런 식으로.

그 다음에 '일로 시작하는 모든 것을 받아와라'라고 했을 때 '일삼보다 작은 것들' 이것만 딱 읽었을 때 내가 지금 '일로 시작하는 모든 것을 받아와야 되는데' '일삼보다 작은 것들에 일로 시작하는 것들이 있을 수가 있으니까' 일단 여기 와서 모든 것들을 다 찾아보면 다 그 다음에

네. 여기 보시면은 이렇게 와서 11호 포인터로 와서 1,3 이렇게 찾고 그 다음에 이제 여기부터는 1보다 큰 것들이니까 앞에 키가 1보다 큰 것들이니까 무시하고 읽지 않아도 되겠죠. 이런 식으로 찾으면 되고요. 그 다음에 이거 보시면은 우리가 이제 어떤 컵깍기로 만들어졌을 때 프리픽스 구간을

이렇게만 쓸 수가 있다고 되었는데 아까 말씀드린 대로 ABC 쓰거나 A,B 쓰거나 A 쓰거나 이건 되는데 뒤에 있는 것들로는 잘 안된다고 했는데 잘 안되는 이유가 앞에는 뭔지 모르겠는데 1로 검색하고 싶다. 이게 지금 두 번째 키가스로 검색하겠다는 거잖아요. 그러면은 여기에 1로 시작하는 1,1이 있을 수도 있으니까 여기도 와봐야 되고 그리고 2로 시작하는 무언가 있을 수도 있으니까 여기도 와봐야 되고 그리고 3로 시작하는 무언가 있을 수도 있으니까 여기도 와봐야 되고

여기도 뭔가 있을 수 있으니까 놀고 놔봐야 하고 결국에는 다 검색해봐야 하는 거예요. 이게 들어오게 되면 어떻게 나올지 모르니까 다 검색해봐야 해요. 그래서 차라리 플루케를 하는 게 더 빠릅니다. 그러니까 이거 한 번 읽고, 이거 읽고, 이거 읽고, 이거 읽고, 이거 읽고 하는 것보다 처음부터 플루케를 하는 게 더 빠른 결과를 얻을 수가 있어요. 그래서 포카키는 이런 식으로

사용할 수가 있는데 이게 지금 얘기가 구체적이지 않아서 감이 잘 안 오실 수도 있을 것 같은데요

그래서 이게 지금

첫 번째 항목이 학과였고, 두 번째 항목이 이름이었다고 한다면, 이런 복합키로 구성된 인덱스가 아니라고 한다면, 학과와 인덱스를 만들어서 동작했을 때, 그 해당되는 학과에 굉장히 많은 학생들이 있겠죠. 그리고 이름으로 된 인덱스가 있을 때, 이름에 따른 동명이 있을 경우에 그 이름에 해당하는 여러 학생들이 있을 거예요. 학과 인덱스를 통해서 학과에 있는 학생들은 이만큼 얻어오고, 이름도 이만큼 얻어와서, 여기서는 주목되는 게 있으면,

중복되는 게 있어야지 그에 해당하는 학과의 특정 이력에 들어서 소프트웨어의 홍길동이라고 하면 소프트웨어의 학과에 있는 모든 학생들이 다 얻어오고 홍길동에 해당하는 모든 학생들이 다 얻어와서 이 둘이 만족되는 사람들을 찾아내야 되는 번거로움이 있는데 복합인덱스를 만들게 되면 바로 이렇게 학과 이름이 있을 때 이게 2번 학과의 2번 이름이 있다고 했을 때 바로 와서 여기서 한 번에만 읽어서 찾아올 수가 있거든요. 그래서 복합인덱스가 좋습니다. 이런 두 개의 어트북도 다 사용하는 경우에는 이게 더

좋고요. 대신에 단점이 뒤에 있는 것들만 하겠다고 명령이 들어오게 되면 약간 흔들릴 수가 있는데 거의 지원하지 않는데 스키스팅이라는 것을 이용해서 아까 보시는 것과 비슷한데 앞에 있는 것을 무시하고 뒤에 있는 것들을 다 검색하도록 해서 이런 식으로 보는 것을 다 얻어오는 형태로 할 수가 있어요. 비율적입니다.

그 다음에 b+tree에 주목된 킷값이 있을 때 어떻게 할까 이렇게 있는데요. 우선 첫 번째로는 레코드 id를 붙이자 라고 되어 있는데 킷값의 레코드 id는 페이지 번호랑 해당되는 정보가 어느 페이지에 저장되어 있는지 그리고 그 페이지의 몇 번째 툴프린지 페이지 번호랑 오프셋으로 구성된 데코드 아이디를 키 값에 덧붙이면 돼요.

키가 유일해지겠죠. 무슨 말인가 하면 키가 이름이었다 라고 한다면 예를 들어 홍길동이었다 라고 한다면 홍길동이 여러 명이 있어요. 홍길동이 여러 명이 있으면 분간이 안 되는데 어떻게 한다고 하냐면 이 홍길동은 첫 번째 페이지에서 백 번째 튜토리이고 이 홍길동은 두 번째 페이지에서 300번째 튜토리다 이런 식으로 이 decode 아이디를 덧붙여준다는 뜻입니다. 덧붙여주게 되면 얘랑 가발이 달라지게 되겠죠. 얘랑 달라져서

다 똑같은 키가스에 비쇄가 될 수 있는데, 모두 피해갈 수 있어요. 모두 다 다른 키가스에 지닌 수 있도록 만들 수 있고요. 여전히 투표를 찾을 때 파셜키로 찾을 수 있다. 홍길동을 했을 때 이것도 찾을 수 있고, 홍길동 따라가면 이것도 같이 있잖아요. 전체를 쓰지 않고도, 레코디아이디가 쓰지 않고도 찾을 수 있다는 것이고요. 하지 말아라 라고 되어 있는데, 오버플로어 리포 노드를 마련하는 방법도 있습니다.

Vielen Dank.

Thank you.

요거플로우 리프 노드부터는 이 상태에서 6을 입력하고 싶다 라고 하면 6은 5와 9 사이에 6이 들어오게 되겠죠. 여기서 저장해야 되는데 6이 중복되는 게 있잖아요. 그러면 요거플로우 리프 노드로 만들어서 여기에 2에 붙여서 6을 추가로 저장하게 됩니다. 이렇게 하게 되면 관리하기도 힘들고 그래서 이렇게 하지 마라 라고 되어 있습니다. 그래서 레코드 아이디를 덧붙여라 하는 것은 여기에다가 1로만 되어 있는데 1에다가 뒤에다가 레코드 아이디 몇 번째 페이지에 몇 번째 페이지에 다 덧붙이게 되면 또 다른 것들

여기가 일어나면 레코드 아이디에 나는 넷 번째 페이지에 슬롯에 일정하는 것을 덧붙여서 6이 여기 들어오게 되면 가득 차있잖아요. 넷 번째에서 스프릿이 나와있죠. 그래서 7, 8이 뒤로 가고 6인 추가로 들어오게 됩니다. 여기 인원을 적절하게 변경해주셔야 하고, 여기 똑같은 보이는데 뒤에 보시면 몇 번째 페이지, 몇 번째 슬롯을 서로 달라요.

오버플러 리프 노드는 가급적 하지 말라고 했던거구요. 그 다음에 이제 D+T를 쓸 때 여러가지 선택 옵션들이 있는데 노드 사이즈를 어떻게 할 것이고, 그 다음에 뭐 지혈할 때 바로바로 할 것인지, 그리고 이 키 값이 고정 길이가 아니라 가변 길이 없다라고 할 때 어떻게 할 것인지, 노드 하나 내부에서 뭔가 찾을 때 어떻게 찾을 것인지, 그 설명들이 있는데 나와있습니다.

그래서 '노드 사이즈'를 어떻게 할 것인가 라고 되어 있는데, 우리가 디스크는 보통 뭔가 값을 읽어 올 때 페이지 단어를 읽어 온다고 했잖아요. 그런데 한 번 읽을 때, 느리기 때문에 한 번 읽을 때 많이 읽는 것이 유리해서 저장 장치의 속도가 느리면 느릴수록 '노드 사이즈를 강제적으로 키워라' 라고 되어 있는데요. '하드리스크'가 딱 나온다면 1Mbps를 늘려서 한 번 힘겹게 읽을 때, 왕창 읽어서

그 특이의 갭셀은 짧게 해주는 것이 좋고요. ssd라고 하면 10KB 이내로 해주면 좋고 메모리 안에 있다면 메모리가 빠르기 때문에 570B 안으로 해주시면 됩니다. 그래서 그냥 대략적인 가이드 라지로 되어 있는데요. 느리면 많이 키워라 라고 되어 있는데 실제로는 러프 로드, 어떤 작업이 걸리는가에 따라서 최저하게 사이즈가 달라질 수가 있습니다. 그래서 리프 노드에서 스팬이 많이 일어나는지 리프 노드에서 스팬이 많이 일어나는지

혹은 루트에서부터 뿌리에서부터 입자기까지 많이 이용하는지, 어느 것을 많이 사용하는지에 따라서 옵티멀 사이즈가 달라질 수 있다는 것입니다. 그 다음에 merge를 하게 되면 우리가 삭제할 때 merge가 가능할 수 있잖아요.

- Okay.

이 상태에서 19를 지우게 되면, 지금 층이 3개죠. 목표가 3인데 19를 지우게 되면 굉장히 많은 변화가 일어나요. 이렇게 굉장히 많은 변화가 일어나는데, 짧아졌죠. 그런데 이 상태에서 뭔가 삽입되고, 또한 뭔가 삽입되면 다시 층이 일어나야 되거든요. 한 번씩 뭔가 대제적인 변화가 일어나게 되면, 비표소출이 고치면서 굉장히 많은 시간을 쓰게 됩니다.

우리가 가급적 B+Tree의 구조를 바꾸지 말자. 웬만해서 바꾸지 말고 꼭 필요할 때만 바꾸자 라는 생각에 의해서 이런 것을 만들게 된다. 어떤 DBMS 같은 경우에는 절반만 찼을 때, 절반 이상 찼지 않았을 때에도 merge를 수행하지 않을 수 있다 라고 되어 있고요. 보통 보면 B+Tree의 평균적으로 통계를 내보면 B+Tree에 있는 node에

얼마나 많은 키값이 차 있는지 보면 대략적으로 69% 정도 차있다. 그 머지를 최대한 늦추게 되면, 아까 보신 바와 같이 19%를 지었을 때 굉장히 많은 변화가 일어났는데, 머지를 늦추면 우리가 큰 변화에 사용되는 시간을 줄일 수가 있습니다.

여기서 19를 지워라 했을 때 그냥 19를 지우고 지금 절반이 안 차이는데 그냥 허용하는 거예요. 이렇게 해 주게 되면 빨리 끝나죠. 그런데 19를 지워서 변경시킨 다음에 다시 무언가 집어넣고 집어넣을 때 다시 커지잖아요. 다시 커지는 것을 해 주게 되면 굉장히 속도가 느려지게 되겠죠. 그러니까 먼지가 일어내야 했을 때 그냥 그것을 놔두는 것이 더 좋을 수도 있다.

그리고 주기적으로 한 번씩, 그러니까 언더필드, 그 반 이상 차지하는 것들을 허용하고, 주기적으로 필요할 때 다시 리빌드하는 전략을 쓰기도 합니다. 그래서 non-balance_tuture 이라고 해서 post_greSQL이 이런 전략을 펴고 있습니다. 이렇게 하게 되면 밸런스가 깨질 수도 있겠죠. 그래서 이 전략을 펴고 있습니다. 어쨌든 속도 향상을 위해서 이런 전략을 펼칠 수도 있습니다.

반드시 절반 이상 하지 않으면 머지 하고 이런 작업을 해야 되는데 그러면은 이제 기존수트를 고치느라고 시간이 오래 걸리기 때문에 그것을 바로바로 하지 않고 좀 제약 조반이 깨지더라도 가만 놔뒀다가 나중에 한꺼번에 하는 방법을 이제 취할 수도 있습니다. 그 다음에 키값이 고정 길이가 아니라 가변 길이일 때 어떻게 할까 라고 되어 있는데 키값을 직접 저장하는 것이 아니라 키값을 포인터로 저장하자 라고 되어 있어요.

그래서 Ttree라고 분리하게 된다고 나오는데, 메모리에서 동작하는 Dbms, 보통은 디스크에서 동작한다고 가정이 되었는데, 메모리에서 동작하는 형태로 만들 수 있습니다. 그래서 포인터로 하는 방법도 있는데, 이 버스는 주로 나오는 것 처럼, 메모리에서 동작하는 것일 때는 우리의 간식 분야 나뉘게 되었죠. 우리는 메모리에서 동작하는 Dbms를 공부하는 것이 아니라, 디스크에 동작하는 Dbms를 공부하는 것이 아니라,

이 세 가지 형태에 대해서 보시면 되는데 일단 첫 번째 방법이 노드의 크기가 가볍적으로 변하도록 하는 방법이 있습니다. 킷값이 고정되어 있지 않기 때문에 노드가 1mg하면 1mg, 500kb이면 500kb 이런 식으로 노드가 보통 고정이 되어 있을 텐데 킷값의 길이가 나로 변하게 되니까 이렇게 노드도 고정되지 않고 그냥 변할 수가 있는 노드 사이즈를

메모리가 사용하지 않았던 거예요. 이렇게 해주게 되면 메모리 관리할 때 좀 조심해야겠죠. 메모리 안에도 메모리가 페이지 안으로 뭔가 저장이 되게 되는데 그것은 마구 우편 크게 변할 수가 있으니까 조심스럽게 해주셔야 되고요. 그게 아니라 간단한 방법을 페이징 하는 방법이 있습니다. 제일 긴 키값에 맞춰서 제일 긴 키값이 '사람 일입니다'라고 했을 때 보통은 우리나라 한국에 있는 세 글자죠. 그러니까 이들은 세 글자인데

5글자나 6글자 이런 경우도 있잖아요. 최대한 이름이 긴 사람이 6글자였다 라고 한다면 모든 사람이 이름을 6글자로 만들어 주는 거예요. 그래서 홍길동 한 다음에 여기다 00 이런 식으로 의미 없는 어떤 캐릭터를 붙여서 모두 다 똑같이 6글자를 만들어 주는 것이 패팅이라는 게 뭐예요. 그 다음에 힘의 방법이 있는데

여기 보시면 각 킷값에 따라서 value가 값이 달라질 수 있게 되니까 포인터를 유지했잖아요. 이것과 비슷하다고 보시면 될 것 같은데.

Thank you.

배열을 하나 만들어서 여기 첫 번째 원소는 어떤 키값과 어떤 밸류를 지니고 있고 두 번째 원소는 어떤 키값과 어떤 배달을 지니고 이런 식으로 키 밸류 리스트들을 이렇게 포인트로 만들어서 해주는 방법이 있습니다. 실제 키값을 저장하면 키값의 길이가 막 변한다고 했잖아요. 실제 키값 대신에 포인트를 저장해서 이런 식으로 상식되었습니다. 그 다음에 노드 안에서 우리가 이만큼의 노드를 하나 한번 읽어왔잖아요. 이만큼 읽어왔는데 이게 리프 노드였다고 해봐요. 리프 노드에서 이만큼 읽어왔는데

'8'이라는 걸 찾아라 라고 했을 때, 일단 첫번째 방법이 순차적으로 찾는 방법이 있습니다. 순차적으로 4, 5, 6, 7, 8, 8을 읽어 오는 방법이 있는데, 'srmd'을 쓸 수 있다. 'single instruction' 'multiful data'예요. 하나의 명령어를 여러 개의 데이터에 적용하는 방법이 있는데,

벡터라이즈를 할 수 있다. 그러니까 약간 정렬을 쓸 수 있다는 것인데 우리가 네 개 단위로 뭔가 처리를 할 수 있다 라고 하면 첫 번째 4개의 칸에 대해서 8을 지금 8 찍고 있거든요. 8인지 아닌지 검사하는 거예요. 이렇게 나왔을 때 0000 나왔고 그 다음에 8인자인지 구제했을 때 여기 1이 나왔죠. 이런 식으로 하게 되면 이 미니어 서치에 대해서 빠르게 할 수 있습니다.

그 다음에 Binary Search는 Easy 탐색이죠. 중간값 찍어서, 칠보다 크니까 여기가 오고 중간값 찍었을 때 구현하기 나름인데 8로 갈 수 있고 9로 갈 수도 있고 컬러감은 바로 찾는 곳이고 9로 하면 바로 다음 번에 찾는 곳이겠죠. Easy 탐색 할 수도 있고요. 그 다음에 Interpolation, 예상할 수도 있습니다. 그래서 어떻게 할 수가 있냐면은 간단하게 시기에 따라서 해주게 되는데 지금 첫 번째 칸이죠.

두 번째 칸, 세 번째 칸, 네 번째 칸, 다섯 번째 칸. 지금 이 자료 부품을 보면은 맨 앞에 값이 타고 여기까지 10인 것은 우리가 알 수가 있어요. 맨 처음 값과 맨 낮은 값을 한 번씩 읽어요. 그러면은 지금 이렇게 여섯 칸 가는 동안에 강도 안에.

지금 이 값의 크기가 6만큼 증가였죠. 우리가 알고 싶은 것은 과연 몇 칸 가야지 지금 8 찾고 있거든요. 몇 칸 가야지 4에서 8까지 4가 증가할까? 라는 거거든요. 이렇게 생각할 수 있어요. 다시 말씀드리면은 1칸, 2칸, 3칸, 4칸, 5칸 우리가 첫 번째 값이랑 마지막 값은 쉽게 어려울 수가 있어요. 첫 번째 값은 4고, 마지막 값은 쉽게 어려울 수가 있어요. 6칸 가는 동안에 6칸 가는 동안에 6칸 가는 동안에 6칸 가는 동안에 6칸 가는데 과연 몇 칸 가야지 우리가 찾고 있는 4에서 4칸 간에 그냥 8을 찾을 수 있을까?

4가 늘어날까 이렇게 해주게 되면 6 곱하기 역항 가야지 24가 될까 여기 6 곱하기 10만원 사요 이렇게 세게 되면 어? 못 잡았네 이게 8만원 사과

아... 음...

더 봐야 되는지가 아니라 몇 번째 칸일까 인가보네요. 그래서 다시 보시면은

이별 걸 칸에 갔을 때

10-4만큼 증가되어 있었다. 과연 몇 칸 가야지 8-4만큼 증가될 수 있을까? 1번간 갔을 때 이만큼 증가되어 있었는데 몇 번째 칸에 가면 이렇게 증가되어 있을까? 넣어봐서 1번간 갔을 때 이만큼 증가되어 있었는데

상호가 되고 이렇게 되고 이렇게 되고 이렇게 시드레암거든요.

첫 번째 칸에 가면 '너가 찾는 값이 있을 거야'라고 나오는데 예측이 틀리긴 했어요. 이 근처에 오니까 한 칸만 더하면 팔이 나와있죠. 이런 식으로 뭔가 가능해서 바로 어느 지정을 찍게 되는데 그게 말일 수도 있지만 틀릴 거예요. 틀렸지만 그 근처에 있는 것이기 때문에 그 근처에서 찾으면 됩니다. 거기서부터 이어수기 해주시면 됩니다. 이런 방법도 있습니다.

제가 실수를 하긴 했는데 이런 식으로 계산할 수가 있어요.

분포를 보고, 4가 맨 처음이고 10이 일구번째 칸에 있었다고 하면은 8은 대략 몇번째 칸에 있을 것 같다고 예상을 해서 칸에 가서 찾는 방법을, 네, 문젝블레이션 방법을 해보겠습니다.

그 다음에 여러가지 빛발스트리에 사용할 수 있는 최적화 옵션들이 있는데 화장실을 선택해보면 왼쪽에는 포인터 스위즈 링이라는 게 나오고 있는데 이것들 하나하나는 노드라고 보이죠. 원래 노드인데 노드들은 페이지 아이디가 있습니다. 이 노드는 디스크의 몇 번째 페이지에 있고 이 노드는 디스크의 몇 번째 페이지에 있고 디스크의 몇 번째 페이지에 있고 이런 식으로 디스크 페이지 번호를 이용해서

우리가 access 를 하게 됐는데 만약에 해당되는 이 노드가 메모리에 올라와있었다. 버커플 우리가 지금 강의에서 생략했는데 메모리에 자주 사용되는 디스크 페이지들이 메모리에 올라와 있는거에요. 이런식으로 메모리에 올라와 있는데 만약에 우리가 어떤 노드들이 메모리에 올라와 있었다 라고 한다면 우리가 이동할 때 보통은 디스크 페이지를 이용해서 우리가 무언가 정보를 얻어오는데 디스크 페이지 대신에 메모리 주소를 바로 바꿔치기 해서

빠르게 얻어오는 최적화 방법이 있습니다. 예를 들어서, 3에 해당하는 키를 찾아가셨을 때 이걸로 오게 되는데, 이렇게 올 때 이게 두 번째 페이지에 있다. 이런 식으로 되어 있거든요. 두 번째 페이지면은 메모리에 어느 영역에 있다. 이런 식으로 우리가 여러 번 수거를 해서 페이지만 얻어오고 그 페이지가 어디에 있는지 이렇게 변하면서 받아와야 되는데

이렇게 하는 것보다는, 이것도 뮤직디스크 세번째 페이지에 있다. 다 페이지로 되어있는데, 이것이 만약에 메모리가 올라 있었다고 한다면, 페이지번호 대신에 메모리 영역을 가리키는 포인터로 대체를 할 수가 있어요. 이런 식으로 포인터로 대체를 하게 되면, 우리가 바로 메모리에서 빠르게 얻어올 수 있겠죠. 그러니까 무슨 말인가 하면, 원래는 뭔가 노드를 읽어올 때 디스크 페이지에 기재되어 있거든요.

페이지 디렉토리를 뒤져봐서 그게 메모리 있는지 없는지 보고 메모리 있으면 얻어오고 아니면 읽어오고 이런 식으로 약간 번거로운 면이 있는데 메모리 있는 거다 라고 하면 페이지 번호를 쓰고 대신에 아예 이렇게 메모리 가리키는 포인터로 바꿔버리면 우리가 이거 읽어올 때 바로 메모리가 있으면 바로 읽어오면 되잖아요. 페이지 번호를 쓰고 페이지 디렉토리를 뒤져보지 않고 그래서 우리가 빠르게 할 수가 있는데 이게 하나하나가 엄청나게 큰 오버헤드 까진 아니에요.

페이지번호를 보고 찾아오는게 엄청난 오버헤스는 아닌데 이제 이런 작업을 굉장히 많이 하게 된다고 수천번, 수만번 하게 된다고 하면 그게 누적돼서 많은 차이를 보일 수도 있기 때문에 이렇게 포인터 스위치를 통해서 페이지번호 대신에 메모리 주소를 바로 가리키도록 해서 빠르게 한 번에 읽어올리게 만드는 최적화 전략을 펼칠 수가 있습니다. 그리고 또 다...

감찰할만한 상황이 있었는데, B+Tree를 변경시키는 것은 노드를 split와 merge를 해야해서 굉장히 비싼 영상입니다. 그래서 태약의 경우에는 DBS가 전체 트리을 다시 재구성하는 것에 굉장히 큰 안 좋은 점이 발생할 수 있다는 것인데, 그렇게 DBS가 전체 트리을 다시 재구성하도록 만들게 하는 워커가

그 해당되는 작업에 책임이 있다 라고 생각했는데요. 만약에 데이터베이스 DBMS가 업데이트를 딜레이하고 자료 구조를 업데이트한 것을 딜레이하고 그냥 배치로 나중에 시간 널러날 때 한번에 변경사항을 다 처리하도록 하는 것은 어떨까 라는 생각이 있습니다. 무슨 말일까 하면은 뭔가 필요할 때마다 스프릿하고 머지하고 이런 작업을 하는 것보다 살짝 늦췄다가 한가할 때 한 번에 다 변경점을

변경점을 반영하는게 어떨까 라는 것이 있는데 그 생각에서 나온 것이 라이트 옵티마이드드 빅플러스 트립 쓰기에 시작하던 빅플러스 트립이 되었는데요. 변경사항을 바로바로 적용하는 것보다는 키 밸류에 있는 변경사항들을 버퍼에 저장하도록 해주는 그러한 기능을 만들 수 있습니다. 그래서 만약에 업데이트가 있었다 라고 하면은

버퍼가 가득 찼으면 위의 단에서 아래가 내려보내는 작업을 할 수가 있는데 예제를 통해서 보시면 될 것 같아요. 보통 인어 노드에 이런 로그, 변경사항을 기록할 수 있는 로그를 저장할 수 있는 칸을 만들어 놓습니다. 루트와 인어 노드에 그래서 7을 넣고 싶다고 했을 때 원래대로라 하면 밑에까지 7을 넣어야 되잖아요. 그런데 그걸 반영하지 않고 그냥 여기 로그 접는 칸을 넣는 거예요. 칸을 팔팍했다. 이런 식으로 해놓고 그냥 끝나요.

10을 지우겠다. 원래는 라인을 지워야 되는데, 여기다 써놓고 뜯네요. 10을 찾아온다고 하면, 딱 왔을 때, 원래는 밑에까지 내려가서 찾아야 되는데, 여기 오니까 10이 지워졌다고 되어있죠. 바로 리턴할 수가 있어요. 40을 넣겠다고 확인되면, 여기다 기재를 하려고 보니까, 여기가 가득 찼잖아요. 원래는 밑에까지 내려가서, 밑에까지 만들어주고, 40을 밑에까지 내려가서.

이렇게 하게 되면 밑에 단에 변경점을 가하지 않고 그리고 트리가 커지고 작아지고 하는 걸 하지 않고 우리가 변경 사항들을 이런 식으로 다 기록을 해 줄 수가 있어요. 이것들을 모아 놨다가 시간 날 때 한 번에 이걸 다 실제로 반영을 하면 되겠죠. 트리 재고생하면 시간 날 때. 그리고 이제 파셜 인덱스라고 해서 인덱스를 전체를 다 만드는 것 대신에 택스한 경우에만 인덱스를 만들 수도 있습니다.

그래서 우리가 a라는 attribute와 b라는 attribute에 대해서 인덱스를 만들어라 라고 되어 있는데 다 만드는 것이 아니라 그 sp의 c값이 utang인 경우에만 만들어라 라고 할 수가 있어요. 무슨 반응을 하면은 이건 약간 좀 와 닿지 않는데 인덱스를 만들 때 그래서 이름에 대한 인덱스를 만들 거예요. 학생 데이터베이스고요. 학생 릴레이션이고 이름에 대한 인덱스를 만들게 되면은 우리가 빠르게

이름을 가지고 어떤 학생을 빠르게 찾아올 수 있죠. 이름에 대한 인데스를 만들 때 인데스를 만드는 명령을 칠 때 '매어 학부는 소프트다'라고 하게 되면 이름에 대한 인데스를 만드는데 소프트웨어 학부 학생한테만 만드는 것이 되겠습니다. 예를 들어 이름 범죄기 '아 나는 소프트웨어 학부 학생만 관심이 있어'라고 한다면 이렇게 소프트웨어 학부를 써주게 되면 소프트웨어 학생에 대한 이름만, 유령으로만 할 수가 있습니다.

이걸 언제 쓰느냐? 보통은 어떤 일자 기준으로 뭔가 검색을 할 때 사용할 수 있기도 한다. 예를 들어서 연도 2025년이나 2026년 기준으로 별도의 인데스를 만들고 싶다. 그래서 이렇게 연도나 월 기준으로 우리가 검색이 많이 일어난다고 생각할 때에는 연도 기준으로 만들어서 더 빠르게 우리가 뭔가 할 수가 있을 거예요. 그러니까 무슨 말인가 하면 어떤 사람의 구매 내역으로 어떤 사람의 구매 내역을 빠르게 얻을 것이다 라고 했을 때

2026년만 가지고 인덱스 만들고, 2025년 가지고 인덱스를 만들고, 이런 식으로 인덱스를 따로 만들게 되면 더 빠르고 효율적으로 우리가 값을 얻을 수가 있겠죠. 그래서 이런 식으로 전체에 대해서 만드는 것 대신 일부에 대해서만 인덱스를 만들 수 있습니다. 그래서 이렇게 인덱스를 만들어주고 검색을 하게 되면 c값이 울탱이 되니까 인덱스 사용에서 빠르게 얻을 수가 있고요.

이렇게 하게 되면 우탱에 대해서 만들어야 하기 때문에 이 인덱스를 가지고는 빠르게 검색을 할 수는 없어요. 그리고 인덱스인데 어떤 include column이라고 해서 column을 포함하고 있는 인덱스에서 나왔는데 인덱스 올릴 query를 위해서 인덱스만 가지고 지리분을 처리할 수도 있거든요. 그 경우에 따라서 인덱스만 가지고 지리를 빠르게 처리할 때 인덱스 인플루즈 클럽을 만들 수 있습니다.

예를 들어서 A라는 attribute랑 길이라는 attribute를 통해서 C값을 얻어 오는 작업을 하고 싶어요. 검색은 이 둘로 하고 C값을 얻어 올 거예요. 예를 들어서 A가 이름이고 D가 학과였다고 하면 C가 수강학습이라고 할 거예요. 그러면 이름과 학과로 빠르게 무엇을 얻을 수 있는데 보통 이 include index가 없으면 이름과 학과 가지고 빠르게 tuple을 얻어 오고 if node 가면 그 tuple이 어디에 있는지 저장되어 있거든요. if node 가서

실제로 저장된 값을 얻어와서 수강점을 얻어왔어야 되는데 이렇게 include를 쓰게 되면 리프 노드에 c까지 같이 들어가있어요. 수강점까지 같이 들어가 있어서 굳이 진짜 데이터를 찾아보지 않고도 빠르게 imbs 안에서 다 해결할 수가 있습니다. 그래서 리프 노드 안에 c값이 실제로 저장되어있다. 검색할 때 사용할 수는 없는데 이렇게 저장되어있어서 이것을 빠르게 보도할 수 있고 search로 사용할 수 없다고 되어 있어요.

드리문이 들어왔다고 하면 이것은 터치키로 사용될 수는 없기 때문에 이것을 환영할 수는 없습니다.

그래서 만약에 모든 어트립이 커리가 필요로 하는 모든 어트립들이 인덱스에 하나 있다라고 하면 실제로 투표를 얻어 올 필요가 없다. 그런 경우에 커버린 인덱스나 아님 인덱스 올 스탠이라고 합니다. 구체적인 교체가 안해서 약간 와닿지 않을 수가 있는데요.

제가 본 예제가 이름이었고, 이게 학과였고, 이게 수강학점이라고 하게 되면 이름학과를 통해서 수강학점을 검색하게 되면 바로 인덱스 안에서 이걸 다 처리할 수가 있거든요. 그래서 빠르게 무언가를 처리할 수가 있는데 이름학과 가지고 도색한 다음 학권을 얻어라 라고 하게 되면 인덱스 안에서 처리가 불가능하죠.

이름이랑 학가로 검색한 다음에 수강 학생까지 저장이 되어 있는데 학번은 없어요. 그럼 학번을 얻어 오기 위해서 포인터를 따라가서 뭔가를 이루어야겠죠. 그래서 거기서는 빠르게 처리가 불가능한데 만약에 빠르게 처리가 가능했다, 필요한 게 다 있었다 라고 하면 우리는 index.all.scan이라고 이름을 붙인다. 그 다음에 리프 노드 값에 실제로 모은 거에요. 리프 노드에 실제로 키들이 막 저장이 되어 있는데

스트레인이라고 한다면 순차적으로 정렬이 되기 때문에 비슷한 값들을 공유할 가능성이 있습니다. 우리가 단어를 저장한다고 하면, 'globd', 'loving', 'robot' 이런 식들이 있을 때 비슷한 단어도 공유하고 있죠. 실제로 이것들을 다 저장하는 것 대신에 공통되는 것은 'rob'이고, 첫 번째는 'bid', 'bid' 이런 식으로 저장 공간을 결합할 수 있어요. 중복되는 것을 앞으로 빼서, 이런 식으로 공간을

여러가지 베리에이션들이 있는데 이런 식으로 공간을 아낄 수가 있습니다. 압축을 할 수가 있어요. 그리고 이제 duplication은 복제인데 복제를 하지 않는 것. 만약에 인덱스가 유니크하지 않은 중복되는 키값이 있었다고 한다면 이런 식으로

중복되는 킷값에 대해서, 예를 들어 홍길동이 여러 번 나올 수도 있죠. 홍길동이 나오고 이렇게 다 다른 밸류들이 있을 수가 있죠. 첫 번째 홍길동은 어떤 사람이고, 두 번째 홍길동이 어떤 사람이고, 세 번째 홍길동이 어떤 사람이고, 이런 식으로 생각하는데 이렇게 있을 때 이것을 중복을 여러 개 써서 저장 공간을 남기하는 것보다는 흔질성은 안 줄어들고, 그것을 리스트로. 해시 테이블에서 똑같은 킷값에 대해서 리스트를 연결하잖아요. 비슷하게 리스트를 연결하자. 라고 해서

첫번째 키값은 이러한 밸려드로 있다. 이런 식으로. 아, 링크될스는 아닙니다. 그냥 연결된 하나의 키값에 대해서 연속적으로 밸려드로 저장하시면 됩니다. 그리고 이제 서픽스 트럼케이션이라고 있는데 프리피스는 앞에 있는 거고 서픽스는 뒤에 있는 거죠. 우리가 이 키가스를 이렇게 저장할 때

보통 이 앞에 단만 넣어서 내가 뭐 CAT를 찾고 있다 라고 하면은 그냥 ABC만 봐도 ABC만 L라는 분 봐도 CAT 위로 가는구나 알 수 있잖아요. 굳이 뒤에 거까지 다 볼 필요가 없잖아요. 그래서 우리는 킥 가서 다 볼 필요가 없다. 그래서 우리는 적당히 앞에 부분만 적당히 프리패스 부분만 저장을 하면은 충분하다 라고 되어있어요. 그래서 이렇게 ABC만 가지고 CAT 왔을 때 이리로 이용하면 되겠죠. 여기다가 벌크 인서트 강인데 벌크 인서트는

몸통이로 굉장히 많이 삽입을 해주는 것인데 우리가 b+tree를 빌드하는 가장 빠른 방법은 키를 정렬한 다음에 그 다음에 bottom-up으로 만들 방법이 있다. 예를 들어서 키가 3,7,9,13,6 이렇게 있으면 정렬을 하면 1,3,6,7,9,13 이렇게 나오죠. 그러니까 1, 3, 4, 10장을 이렇게

리프트 부터 만든 다음에 거슬로 올라가서 만드는 방법이 있습니다. 우리가 보통은 이렇게 기값이 있을 때 3 입력하고 7 입력하고 9 입력하고 이런 식으로 하나씩 로트부터 만들어야 되잖아요. 그런 식으로 하나 하기보다는 우리가 뭉텅 위로 그냥 처음부터 뭔가 기펄트를 만들어야 된다고 하는 뭉텅 위로 들어왔을 때 정리하고 리프트 부터 만든 다음에 바탕으로 이렇게 바로 만드는 것이 빠르다.

데모는 생략하기로 하겠고, 결론이, B+Tree는 DDS를 만들 때 좋은 자료 고조다 라고 하겠고요. 그리고, 동시성 제어. 그러니까 여러명이 B+Tree를 읽고 쓰고 할 때, 그것을 지원하도록 만든 것은 조금 어려운데, 우리는 이거 생략하도록 하겠습니다. - 감사합니다.

생각보다 시간이 오래가는데 원래 커리 프로세싱까지 하려고 했는데 커리 프로세싱은 비디오 면으로 진행하도록 하겠습니다. 그럼 여기서 마치겠습니다.