hash table + index

테이블에 대해서 하고 있는데요. 간단하게 보실 수 있고, 진도가 완성을 하겠습니다.

해시가 많은 원하는 자료를 얻을 수 있습니다. 그런데 최악의 경우는 계속해서 다음 칸을 찾아가야 하기 때문에 오류로 몇 칸을 그릴 수 있는데 일반적으로는 상륙시간이 많이 찾아올 수 있고 공간 복잡도는 당연히 N개 자장하면 N개의 기대하는 만큼의 공간이 필요합니다. 해시 테이블을 구성하는 요소는 크게 두 가지가 있었는데요. 첫 번째에는 해시 함수였고 두 번째에는 스킨이에요.

시함수는 함수이기 때문에 입력과 출력이 있는데 입력으로는 축값이 입력이 돼요. 축값은 텍스트가 될 수도 있고 영상이 될 수도 있고 음원이 될 수도 있는데 컴퓨터 입장에서는 뭐가 됐던지 간에 다 0과 1로 이루어진 숫자이기 때문에 결국에 숫자를 입력으로 가는 것이고요. 그 다음 숫자를 출력하는데

너가 찾고 있는 키값은 몇 번째 칸에 가봐 라고 하는 인덱스를 출력해요. 어떤 off-set이나 인덱스를 출력해서 이 해시함수가 알려주는 몇 번째 칸에 가게 되면 이 키값에 해당하는 자료가 거기에 위치하고 있습니다. 이런 해시함수가 있고 그 다음에 해시함수를 사용하다 보면 충돌이 발생할 수 밖에 없거든요. 예를 들어서 우리가

학번과 학번에 해당하는 이름을 저장한다 라고 하실 때에 키고 저장한다고 했을 때 어떤 학번에 대해서는 7번째 칸의 가방이라고 시험성 알려줬는데 다른 학번에 대해서도 7번째 칸의 가방을 알려줄 수 있거든요. 그렇게 되면 충돌이 발생하는 것인데 충돌이 발생했을 때 어떻게 할 것인지

그것을 말해주는 것이 쉐싱 스킴에요. 쉐싱 스킴에는 두 가지가 있다고 했는데 정적인 상태, 테이블 사이즈가 고정되어 있는 백 칸에만 백 칸, 이백 칸에만 백 칸이 고정된 상태에서 충돌을 해결하는 방법이 있고 자유롭게 테이블 사이즈가 변화하는 상황에서 그 충돌을 다루는 방법이 있습니다.

그래서 고정된 것은 배열을 사용하는 것이고 자유롭게 테이블 사이즈에 관한 것은 링크리스트 사용한 것이라고 매치간에 말씀을 드렸어요. 해시 함수는 어떤 키가스를 받아서 링크지절을 내놓는다. 링크지절을 내놓는다. 스태틱 캐싱 스킵은 배열을 쓰는 테이블 사이즈에 고정된 것이었는데

이형 프로그랜싱은 충돌 발생했을 때 한 칸 밑으로 내려놓은 것으로 해결했고요. 그 다음 물근노트싱은 한 칸씩 밀려나가다가 불쌍하게 했을 경우에 대해서 이는 뒤는 한 칸 밀려나는데 이는 한 칸 두 칸 밀려났죠. 불쌍하기 때문에 불쌍한 것이 자리를 빼와서요.

세 카누로 밀려나기 전에 여기에서 발을 떼왔고 원래 인터넷 밀려나서 두칸 밀려나게 됩니다. 이런 식으로 불쌍한 힐을 우대하는 그런 정책을 표현하는 것이 로빈헤싱이었고요. 아까 보신 로빈헤싱과 리니어헤싱을 보시면 다 이상적인 자리에 있을 수도 있지만 이렇게 이상적인 자리가 아니면 몇 가지 떨어져 있을 수도 있어요.

그리고 3명의 저하가 오기 때문에 그 문제를 해결한 것이 쿠쿠헤싱이었어요. 쿠쿠헤싱은 무조건 최적의 장소였습니다. 찾을 때나 삭제하고자 할 때 단번에 우리가 어디에 있는지 알아와서 탐색도 되고 지우는 것도 되는데 문제는 삽입할 때에요. 삽입할 때는 약간 시간이 오래 걸릴 수가 있어요. 그래서 테이블을 여러 개 유지하는 두 개였다고 했을 때 각기 다른 해시가프를 써서

그래서 A는 첫 번째 시스템으로 두 번째 간, 두 번째 시스템으로 네 번째 간이 되어서 둘 다 비어있으면 아무데나 들어가고, 그 다음에 항문형 비어있으면 비어있는 대로 들어가고, 양쪽 다 뭔가를 차지하고 있다면 랜덤하게 한 자리를 빼앗습니다. 빼앗고, 쫓겨나니까 또 자리를 빼앗고,

남의 빈자리로 들어가는 이렇게 되는데 어쨌든 사업할 때 이렇게 복잡할 수 있지만 무조건 다 최적의 장소에서 찾을 수 있다. 여기나 여기 있다고 했는데 여기를 찾을 수 있다. 무조건 최적의 장소에 위치해 있기 때문에 빼서서라도 들어가니까 최적의 장소에 있기 때문에

때문에 탐색과 삭제는 굉장히 빠릅니다. 그래서 아까 보신 세 가지 스태틱한 해싱 스킹을 사용할 때에는 테이블 사이즈를 누리거나 주둘때 다시 오는 키들을 다시 집어넣어야 되는 리빌딩해야 되는 단점이 있습니다. 그래서 속도가 누려질 수가 있는데 다이아믹스 테이블은 이러한 단점을 보완하고 있어요.

chaindacing, extendable, and linear system. chaindacing은 linktrist를 활용하는 건데요. 어떻게 collision을 해결하냐 하면은 같은 버킷에 오는 키들을 다 똑같은 linktrist에 넣어버리는 거예요. 되게 단순한데

이제 보시면 쉬울거에요. 데이를 패션자한테 물어봤더니 두 번째 슬롯에 넣으래요. 그래서 여기다 넣습니다. 각각이 다 링크 리스트에요. B는 첫 번째 슬롯에 넣으래. 링크 리스트에 넣었고 C, 아까 A형 충돌이 일어났죠. 충돌이 일어났는데 그냥 링크 리스트에 넣는 것을 해결해요.

이 부분은 충돌이 일어나는데 리스트에 적어주고 충돌이 일어나는데 리스트에 적어주고 이런 식으로 충돌을 해결합니다. 이것과 단점은 계속해서 여기가 들어온다고 하게 되면 무한정 길어지게 되죠. 계속 길어져요. 그래서 내가 뭔가를 찾고자 했을 때 여기로 빠지게 됐다 그러면 이걸 다 뒤져 봐야해요.

굉장히 늘려지게 되죠. 그니까 Pitch Tab을 빠르게 쓰려고 쓰는 것인데 이렇게 일로일로 초 리스트 플로우가 늘어져 있으면 굉장히 늘려지는 단점이 있어서 그 단점을 보완하고자 나온 것이 E-Stand-up을 핵심이 되겠습니다. Chain Facing은 무한적 무한이 리스트가 커지는 단점이 있을 것인데

Extendable Heasing은 어느 한 슬롯이 굉장히 커지면 스프릿하게 됩니다. 분할해요. 그래서 이것도 예제로를 통해서 보시면 될 것 같은데 Extendable Heasing에는 카운터가 존재합니다. 글로벌 카운터가 있고 로벌 카운터가 있는데 여기 나와있는 곳은 키값이에요. 키값은 0과 1로 이루어진 칫자로 나타내진다고 했죠. 컴퓨터 입장에서는.

어떻게 보시면 되냐면은 여기 키값이 0,0으로 시작한다. 그럼 첫 번째 칸이고요. 0으로 시작한다면 두 번째 칸이고 1,0, 세 번째 칸은 1,2,4번째 칸입니다. 그래서 0,0과 0을 같은 데에 가르치고 있어요. 그렇기 때문에 앞자리가 0으로 시작하면 똑같은 데를 의미해요. 똑같은 데를 가르칩니다. 그래서 이 자리 보시면은

그러면은 로컬 카운터가 1일 때 우리는 영어로 시작해 라고 알려주는 거예요. 여기는 일단 국한발리니까 난민이 1 0으로 시작하는 거예요. 1 0 시작하는 게 1일 때 카운터가 1일 때 가장 큰 로컬 카운터가 1일다 나와있고요.

따라가서 여기서 연기를 있는 용을 이렇게 넣을 수 있고요. 1 0 1 1 1을 삽입하고 싶다. 1 0 1 1 1은 여기서 시작하니까 여기서 집어넣을 수 있습니다. 집어넣었고요. 1 0 1 1 정도 집어넣고 싶다고 했는데 지금 보시면 여기 한 칸이 3개씩 밖에 안 들어가는데

여기로 할 땅이 되어서 여기로 들어가야 되는 일이 생겼어요. 가득 찼기 때문에 아까 체인 대신 같은 경우에 계속 이어붙여 주게 되는데 이어붙여 주면 퍼포먼스가 떨어진다고 했죠. 이어붙여 주는 거 대신에 여기를 자리에 쪼갠다. 스플릿을 하게 되는 거예요. 그래서 지금은 두 칸까지만 보고 있는데 두 칸까지만 봤을 때는

이렇게는 다 똑같죠. 10101010 똑같은데 3칸을 보게 되면 다른 애들이 생겨요. 3칸을 보게 되면 10101010101010 이렇게 색상을 보도록 만들어주면 로버플러가 발생해서 일단 첫번째 글로벌 카운터를 늘려주고 이렇게 글로벌 카운터를 이제 3칸까지 보는 애가 생겼어. 한번 늘려주고 이렇게 0000 이렇게 확장시킵니다.

확장을 시켜서 여기가 이제 3칸씩 보는 애들이죠. 3칸씩 보는 애들이 1년 0, 1년 1, 2년 1 스플릿이 되고 원래 0으로 시작한 애들 다행이 똑같이 가리키게 되어있고요. 그 다음에 1, 2, 1에서 가리키는 애들 여기 가리키게 되어있고 새로 생긴 1년 0과 2년 1은 이렇게 가리키게 되어있습니다.

그래서 이렇게 동작하는 것이 extendable 해싱입니다. 그래서 무엇인가 키가 많이 들어온다. 그래서 거기가 넘쳐나다 하면 거기를 스플릿해서요. linear 해싱은 extendable 해싱이랑 좀 다른데 extendable 해싱은 무엇인가 문제 생기지를 스플릿하는 반면에

리니어 해싱은 프린터와 가리키는 것을 스플릿해요. 약간 생뚱맞은 때를 스플릿한다는 거에요. 문제 생긴 데가 스플릿되는 게 아니라 그렇게 예제를 통해 보시면 될 것 같은데 리니어 해싱은 일단 간단하게 해시 함수를 모듈로 쓴다고 가정하고 있어요. 모듈로 4를 쓰고 있는데

10값을 살아나서 나머지가 0이면 여기, 1이면 여기, 2이면 여기, 3이면 여기. 이렇게 다 기억이 되어있어요. 6을 얻어보시라고 했을 때, 8시압스 적용하니까 2가 나왔죠. 두 번째 가능하면 6이 오기 있어요. 6을 찾아볼 수가 있고요. 10시를 넣고 싶다. 살아나서 나머지 1이기 때문에 여기로 들어가면 되는데 가득 차있죠.

스탠더레싱이라면 스프릿해서 잘 쪼갤 텐데 스프릿 포인터가 가리키고 있는 것을 스프릿합니다. 그래서 어떤 일이 발생하냐면 오프로는 이렇게 연결해주고 캐시 함수를 3명 하나 보이대요. 원래 모두 4만 있었는데

이 팔을 생기면서 여기 스플릿합니다. 얘가 쪼개지게 되는데 8로 나눴 때 나머지가 0이면 여기. 8로 나눴 때 나머지가 4가죠. 4면 여기. 이렇게 쪼개지게 됩니다.

이런 식으로 쪼개지게 됩니다. 이 상태에서 20을 얻어 오셨다 라고 하게 되면 쪼개졌으니까 다음번 스프릿은 얘가 할 차례 하고 스프릿 포인트가 내려가요. 이 상태에서 20을 얻어 오셨다 라고 했을 때 첫 번째 시험에서 적용하니까 0이죠. 그래서 여기로 갔는데 얘는 이미 스프릿 된 걸 알잖아요. 포인트가 붙이고 있으니까 이미 스프릿 된 거라서

두 번째 해시에서까지 써야 되는구나. 두 번째 해시에서 적으면 사과 나옵니다. 그래서 네 번째 칸에 가서 읽어보게 됩니다. '부'를 읽어봅시다. 라고 했을 때 '부'는 살아나서 나머지 이기 때문에 이렇게 들어오게 되고요. 그래서 차이가 있는데 extendable 해싱은 문제가 생긴 부분을 스피릿하고 linear 해싱은 문제가 생기지 않은

않은 다른 곳을 스프릿하게 되는데 우리가 해시 전략의 성능을 평가할 때 벤치마클 데이터셋을 사용하게 되는데 어떤 벤치마클 데이터셋은 공격한 데를 계속 공격하고 어떤 벤치마클 데이터셋은 공격하다가 한참 공격하고 또 다른 데 공격을 계속 공격 리치를 바꾸는 것입니다.

수 있는 데이터제도 있어요. 근데 계속해서 똑같은 점을 공격한다고 하면 이 3dm 랜싱은 지금 문제 된 데를 바로 해가기 때문에 대처를 빨리 빨리 잘 할 수 있는 반면에 리니얼싱은 엉덩한 데서 필수 하잖아요. 그래서 엉덩한 데서 필수해서 문제가 되는데 또 반대로 막 공격이 일어나다가 다른 데를 공격하는 알고리즘 같은 경우에는

스탠더블 히스는

지금 막 공격 일어났던데만 스프릿했기 때문에 다른 곳에 공격되면 속속무치가 당하겠죠. 그래서 다른 곳에 스프릿했는데 다른 곳에 공격이 들어와요. 그러면 얘는 또 당해요. 얘는 소일코 외양관 꽂히는 그런 알고리즘이니까 당하는데요. 인이언이싱 같은 경우는 미리 준비를 해놓기 때문에 다른 곳에 공격이 들어왔을 때 대처를 잘 할 수가 있습니다.

각기의 장략적이 있는데 데이터셋의 유형에 따라서 어떤 것이 더 분리하고 정해지는데 미리 어떤 것을 써야지 좋을지는 알 수는 없습니다. 그래서 차이는 있습니다. 스탠더패싱은 오고플러 발생한 데 스플릿하고

하고 비교했으면 그냥 순차적으로 하나씩 하나씩 스피트한다. 기억을 하시면 되고요. 언젠가는 얘도 하나씩 순차적으로 하니까 5% 발생한데도 언젠간 스피트 일어나겠죠. 그런 얘기가 써있고요. 지우는 얘기가 있는데 지우는 것은 간단하게 나와 있는데 약간 좀 복잡하거든요. 수염에는 안 나와요. 대충 어떻게 복잡하는지 보시면은

그러면은 인식을 지우겠다 라고 하면은 첫번째 해시항수 이용해서 네번째 칸입니다. 네번째 칸이 생필이 일어나잖아요. 두번째 해시항수를 써야 돼요. 그럼 네번째 칸에 있다 하면서 알아서. 그래서 이제 지우게 되는데 네번째 아무것도 없잖아요. 유지할 필요가 없어서 이제 삭제되게 됩니다. 삭제되면서 이제 수필 포인트에서 수필 나오는 거 거쳐옵니다.

그런데 이제 20일을 넣겠다 라고 하게 되면은 20일은 눌러오게 되는데 살아나서 나오지니까 5% 또 발생했죠. 5% 또 발생해서 다시 스프릿이 이제 일어나게 됩니다. 어쨌든 이런 식으로 동작하는 것을 유명할 수 있는고요. 결론이 해시 테이블은 굉장히 빠른 속도로 탐색이 가능하다. 그래서 dbms 내부에서 사용된다 라고 되어 있는데

디베어스 내부에서 이리젝트 매칭을 사용하는 인덱 조인 만들 때 사용하기도 하고 그리고 조인 할 때도 나중에 나오게 되면 해쉬 조인이 있는데 정확한 값을 빠르게 찾아와서 조인을 하게 돼요. 디스틴트 키워드 처리할 때도 해쉬가 쓰여요. 예를 들어서 셀렉트 디스틴트 네임 하게 되면

그 유일한 이름만 가져오게 되죠. 그런데 이미 내가 한번 본 이름인지 아닌지 빠르게 알아보고 싶을 때 해시함수로 해시 테이블을 만들어주면 빠르게 내가 이미 본 이름인지 아닌지를 알 수가 있어서 키워드를 찾아드리고 여러 가지로 쓰입니다. 해시 테이블은. 속도랑 유연성 사이에서 트레이블 오프가 있다. 문제는 우리가 일반적인 테이블 개수를 만들 때

고성능의 이크젝트 매칭을 지원하는 테이블 인덱스를 만들 때 쓸 수는 있는데 일반적인 테이블 인덱스를 만들 때는 쓸 수가 없어요. 왜냐하면 우리가 지리를 만들 때 연봉이 2000만원부터 8000만원까지 모든 사람들을 가져와라 이런 식으로 하게 되면

그러면 나중에 그래픽 프레스 투인은 이걸 지원하는데 해시 테이블은 이걸 지원하지 않아요. 정확하게 2500에 2500, 3000에 3000 이건 금방 얻어올 수 있거든요. 한 번에. 2000부터 8000 사이에 있는 거 얻어오라고 하면 할 수는 있는데 예를 들어, 정확하게 2001인 거 다 얻어오고 2002인 거 얻어오고 2003인 거 얻어오고

이렇게 빨리 할 수 있는데 시간이 굉장히 어려워 걸릴 거잖아요. 거의 못하는 곳이고. 그래서 해시 테이블로는 range scan은 힘들다. 범위 검색은 쉽지가 않기 때문에 B+T를 쓸 수밖에 없다. 라고 봐서 B+T를 공부하게 됩니다. 강의지를 만드시는 분의 주장으로는 자료 구조를 중에서 가장 유대한 자료 구조를 다.

하고 있습니다. 그럼 이제 비틀스 트리로 넘어가도록 하겠습니다.

그래서 원래는 인덱스랑 필터에 대해서 다 공부를 해야 되는데 시간 관계상 필터는 생략하고 인덱스에 대해서 공부를 할 거예요. 인덱스는 B+3로 부연이 일어나는데 데이터 스트럭처들 중에서 가장 유대한 것이다 라고 나와 있어요. 이 강의자를 만드신 분의 개인적인 생각이고요. 사람마다 생각은 다르겠죠.

해시 테이블을 공부했었는데 해시 테이블은 시간 보셨을 때 일반적으로 5도로 1, 3, 4시간만 가능하다. 충돌 발생했을 때 스태틱하게 해결하는 방법도 있고 다이네마하게 해결하는 방법도 있고 해시 테이블은 주로 내부 기계 구조를 만들 때 사용하고 인덱스를 만들 때에는 디프로스트를 사용합니다. 인덱스가 무엇일까 알아야 되는데 여러분들 정보 설정 보시면 책의 뒷면에

어떤 단어는 몇 페이지 나오고 어떤 단어는 몇 페이지 나오고 이런 세기인 있잖아요. 그런 세기인으로 보시면 돼요. 그래서 어떤 attribute가 학번이 어떤 사람의 각도가 어디인가 그런 것들을 알려주는 것이 인덱스가 되겠습니다. 반면 필터는 어떤 자료가 존재하는지 아닌지는 알려줘요.

학번이 있는지 없는지는 알려주는데 그 자료가 어디에 있는지는 알려주지 않아요. 어디에 있는지 알려주지 않는 것이 필터에요. 있는지 없는지만 알려주고 어디에 있는지는 알려주지 않습니다. 우리는 인텍스에 대해서 공부할 건데요. 그래서 b+tree의 제휴, b+tree를 사용할 때 선택할 수 있는 것들, 최적화,

비틀에는 어떤 특징이 있냐 하면

이 화장이 트리는 이렇게 생겼죠. 반별 설치트리인데 값이 그냥 하나씩 있어요. 25분 25, 22분 20, 17분 10, 이런 식으로 읽는데

빅트리는 노드 안에 값이 여러 개 있습니다. 지금 두 개밖에 없는데 실제는 굉장히 많이 들어있어요. 이렇게 만들어진 이유가 빅트리는 디스크 상에 존재해서 그렇습니다. 디스크 상에 존재하기 때문에 한 번에 읽을 때 여러 개 읽어오도록 되어 있어요. 우리가 비대면 시간에 스토리지에 대해서 공부했는데

디스크에서 뭔가 값을 읽어올 때 읽어오는 값의 단위가 있었거든요. 어떤 단위로 읽어왔어요. 기억하실지 모르겠는데. 김세범 학생 계신가요? 혹시 디스크에서 뭔가 읽어올 때 어떤 단위로 읽어오는지 기억나시나요?

- 하나씩만 정수 하나씩 모으실 수 있는 게 아니고 - 공통률을 모으는데 어떤 단위를 모으실 수 있나요? - 잘 하세요. - 비대면을 들어서 기억이 잘 안 나겠죠? - 홍정택 학생. - 네. - 혹시 기억나시나요? - 잘 기억이 안 나요. - 그렇죠? 네. - 이동연 학생.

동현 학생이 아시나요? 페이지 단위로 읽어봅니다. 페이지 단위로 읽어봅니다. 그래서 디스크에서 뭔가 값을 읽어올 때 25이면 25, 25이면 25, 하나만 읽어올 수 있는 게 아니라 페이지 단위로 읽어보기 때문에 가급적이면 여기 안에 값을 많이 넣어두는 것이 유지해요. 하나만 읽어오는 것보다

이렇게 두 개밖에 없는데 4KB를 가득 채워서 굉장히 크게 해서 여기가 한 마디 싹 읽어오게 하는게 유리해서 이렇게 만들어 놓은 것이 비트리가 되겠습니다. 그리고 이름이 비트리인 이유가 비트리 만든 곳이 보잉사의

저자의 연구소였거든요. 그래서 보임도 B를 시작하기 때문에 비트리다 라는 말도 있고 나중에 나오기 때문에 이게 밸런스 3라서 뿌리에서부터 일쌍기까지 거리가 모두 다 똑같아요. 밸런스가 맞춰져 있거든요. 그래서 밸런스가 맞춰져 있기 때문에 B다 아니면 또 이 맞는 사람 융문 쓴 사람들의 저자에 B로 시작하는 사람이 있어서 그 사람 이름을 따와서 비트리다 라고 하는 썰들이 있는데

정확하게 무엇인지 제작자들이 밝히진 않았어요. 그래서 뭔지는 모르겠지만 어쨌든 ep3는 보통 디스크에서 많이 쓰이는 장로구조가 되겠습니다. 디스크상에 위치한 트리에요. 최초의 에너는 1970년대에 ep3가 나왔고요. 그것을 개랑해서 b+3, 로비스타3, 비행드3 이런 것도 쭉 나왔고요.

우리는 이 b+tree에 대해서 외출을 볼 것이고, 이것도 완전한 b+tree가 아니라 b-linktree의 일부 성격에 가미된 b+tree를 볼 것입니다. 그래서 b-tree가 발표된 최초의 논문이고요.

B+Tree에 대한 설명이 나오고 있는데요. B+Tree는 Self-Balancing, 밸런스가 맞춰져 있다는 뜻이 어떤 걸 읽으시냐 하면은

여기 보시면은 여기 풀리로부터 이사기까지 거리가 다 똑같아요. 한 칸 두 칸, 한 칸 두 칸, 어떻게 맞춰서 다 두 칸이에요. 두 칸인데 일반적인 트리는 그렇지 않죠. 한 칸 두 칸, 두 칸 맞이 갈 수도 있고 한 칸 두 칸 세 칸 맞이 갈 수도 있고 이런 식으로 밸런스가 안 맞춰져 있는데 B+3에는 무조건 밸런스가 맞춰져 있습니다.

뿌리에서부터 밀사기까지의 거리가 다 똑같고요. 그리고 M개의 갈래길이 있다 라고 보시면 되는데 예를 들면 여기 최대 3개의 갈래길이 있는 거예요.

m계의 갈릇길이 있어서 선택 시간은 logo m에 n이라고 되어있는데 일반적인 이진 트리는 여기가 e에요. logo 2에 n인데 지금 m계로 쪼개 쓰고 있기 때문에 logo m에 n이 됩니다. 완벽하게 밸런스가 맞춰져 있어서 깊이가 다 똑같구요. 그 다음에 bootnode는 안 봐야 되는데 다른 node들은 다 절반 이상 차있어야

공식이 나오는데 공식이 약간 잘못됐어요. 그래서 무시하셔도 절반 이상은 차있어야 된다. 이렇게만 아시면 될 것 같습니다. 그리고 k계의 키가 있으면 k+1대에 출투런이 있다. 무슨 말인가 하면, 예를 들어서 키값이 2개가 있으면 자식이 하나, 둘,

하나, 둘, 셋 개 있다는 뜻이에요. 두 개의 K개가 있으면 K+2개의 갈래티들이 있다. 그리고 디스크에 위치하고 있기 때문에 커다란 데이터 블록을 읽고 쓰는 데 최적화 되어 있다. 위에 B+3D의 여러 가지 특징들이 있는데 실제 구현할 때는 이걸 다 지키게 구현을 안 해도 되기 때문에 일부는 강제하지 않고 구현을 해놓은 것도 있습니다.

있습니다. 지금은 무시하고 넘어가야 겠다. 나중에 최적화할 때 나옵니다. b+표기에 예제있게요. 가장 꼭대기에 있는 것이 루트노드. 루트노드는 절반 안차 있어도 돼요. 그리고 중간에 있는 것이 이돈노드 혹은 넷돈 리프노드라고 하는데 그리고 마지막에 리프노드가 있습니다.

위에서 10, 35, 20. 왼쪽이 작고 오른쪽이 큽니다. 루트 노트를 자세히 보면 맨 앞에 두 단에

즉 c 언어의 포인터 표시 같은 게 있죠. 주소를 가리키고 있어요. 20보다 작은 엔드를 가리키고 있는 주소. 키값 있고 주소 있고, 키값 있고 주소 있고 이렇게 반복되고 있고요. 이것도 마찬가지고. 얘는 아랫단 엔드. 유프 노드에 오면 좀 다른데. 얘는 키 밸류 페어드로 이루어져 있어요. 6번에 해당하는 키의 값.

기계 값, 기계 값인 식으로 값이 이렇게 되어 있습니다. 학번이었다고 한다면 6이라는 학번에 해당하는 학생의 정보 이런 게 되겠죠. 10이라는 학생에 해당하는 학생의 정보 이렇게 보시면 됩니다. 실제 데이터는 정보는 가장 밑에 단에만 있다 보시면 되고요.

Okay.

B+Tree는 없던건데 B-Lift Tree에는 sibling pointer라는게 존재해서 옆에 있는 node, 형제노드로 이동이 가능하도록 되어 있거든요. 형제노드로 이동이 가능하도록 만든 경우에는 이와 같이 앞단과 끝단을 주소를 저장할 수 있게 되어 있어요. 그래서 내 앞의 node는 어디로 가면 되고 내 뒤의 node는 어디로 가면 되고

주소 정보도 같이 저장할 수가 있습니다. 어쨌든 밑에다니에서 보면은 낮은 키값으로 커지는 키값으로 단순 증가하는 것을 볼 수가 있고요. p+3의 node. node라고 하면은 이용하지는 node이죠. 이것도 node고 이것도 node고 node에 대해서는 형편을 보겠습니다. 모든 node들은 key value pair로 이루어져 있는데 Diff 노드만 사실은 Key Value Faire로 이루어져 있고요.

키 밸류 페어가 아니라 다른 노드들은 주소로 이뤄져 있어요. 여기는 실제 키 밸류로 이뤄져 있는데 리트 노드는 키에 대한 밸류인데 중간이나 리트 노드는 보시면 주소로 이뤄져 있죠. 키 값보다 크거나 같은 경우 로드를 이용해 나가는 주소로 이뤄져 있습니다. 그리고 배얼들은 보통 정렬된 상태로 이뤄져 있습니다.

그리고 널값이 있는 경우에 널값은 뭉쳐있어요. 가장 첫번째는 가장 마지막에 뭉쳐있어요. 지금 널값이 없는데 예를 들어서 널값들이 맞춘지 했다. 그러면 널값들이 여러개 있는데 널값들을 다 앞쪽에 골아주거나 혹은 다 뒤쪽에 골아들 수 있습니다.

이 안에는 별것을 유치시키지 않는 것입니다. 리프 노드를 보시면은, 리프 노드는 이렇게 보면은, 지금 약간 동그라미하고, 엑셀 표시 같이 되어 있는 것이 포인터예요. 그래서 지금 시플릭 노드, 앞에 있는 시플릭 노드를 가리키는 포인터, 뒤에 있는 시플릭 노드를 가리키는 포인터고요. 첫 번째 키커드에 대한 배율, 첫 번째 배율, 그 다음에 엠벌트 키커드에 대한 배율, 이렇게 배율이 되는 것입니다.

이렇게 value를 실제로 저장할 수도 있어요. 예를 들어서 어떤 학번에 대한 나이, 나이도 써주시면 됩니다. 어떤 학번에 대한 나이 하면 나이도 써주시면 되는데 나이 같은 경우는 integer이기 때문에 32bit 그러니까 4가이로 충분히 저장이 가능해서 이렇게 value를 이렇게 value를 질자로 써줄 수가 있는데

그게 아니라 이 value에다가 지금 자격력을 저장하고 싶다. 자격력을 저장하고 싶다. 라고 하면 어떤 앱권에 다 돌아가도록 해야 되는데 자격력에서는 사람마다 길이가 다 다르잖아요. 그리고 엄청나게 커질 수도 있고 하기 때문에 그 얼마 저장 못하겠죠. 엄청나게 커지면은. 그래서 진짜 value 대신에 이렇게 포인터를 저장할 수도 있어요. 자격력 첫 번째 키 값은 자격력에서는 여기에 가봐.

이 값아, 이 자유성의 값을 하는 포인터로 저장할 수도 있습니다. 포인터로 저장하게 되면 다시 균형하게 많이 저장할 수도 있습니다. 이렇게 간단하게 리프 노드를 만들 수도 있고요. 이렇게 만들 수도 있습니다. 여러가지 메타드 엔터로 들어가고 이 리프 노드는 몇 번째 층에 있고

그 다음에 슬롯이 몇개가 있고 그 다음에 이전 t-value도 다음 t-value도 주소가 있고 그 다음에 제일 높은 key 그리고 key value 표현을 넣는 식으로 만들 수 있고요. 다른게는 이런 식으로 만들 수 있습니다. 그리고 펠류가 반복적으로 나타나는 것이 아니라 key 면 key 면을 넣으면 이렇게 쭉 양결지역합니다.

이렇게 구현할 수도 있어요. 리프 노드 구현 방식이 여러 개 있다. 정도만 아시고 그리고 value에는 실제 value가 들어와도 되지만 value에 해당하는 포인터를 저장할 수도 있다. 이 정도만 아시면 될 것 같아요. 이걸 다 외우실 필요는 없습니다. 그래서 리프 노드 value로는 실제 value가 들어올 수도 있고 포인터 주소가 들어올 수도 있는데 첫 번째 approach가 주소로 포인터를 저장하는 거예요.

그래서 더 흔하다 나오셔야 했고요. 우리가 record id는 페이지랑 그 다음에 offset으로 구성되어 있거든요. 비대면 시간에 했었는데, 디스크의 몇 번째 페이지에 페이지 안에 몇 번째 투플이 다 적혀 있어요.

이 k1의 자동선은 디스크의 일곱 번째 페이지에 열 번째 아이템이다. 이런 식으로 기재가 되어 있어요. 이렇게 하는 게 일반적이고 진짜로 거의 다 데이터를 따라가는 방법도 있는데 이렇게 할 때는

두 가지 가멸 길이 생깁니다. 인덱스가 기본키에 대한 인덱스였다. 학번과 같은 기본키에 대한 인덱스였다 라고 하면은 진짜로 튜플에 대한 내용이 다 저장이 되어 있어요. 학번이었다 라고 한다면은 학번에 대한

학원에 대한 비틀어 비틀어 틀어 틀어 다라고 한다면은 나일뿐만 아니라 그 학생에 대한 모든 정보가 싹 저장이되요. 그런데 그것이 이제 보조인덱스였다. 주인덱스는 보조인덱스 예를 들어서 전화번호라던가 아니면 이름이라던가

다른 attribute로 만들어진 index였다 라고 한다면 리프노드에 진짜 데이터를 저장하는 것이 아니라 기본 키를 저장하고 있다고 되어 있는데요. 이게 무슨 말인가 하면은 학원으로 index 만들었을 때 학원에 실제 모든 데이터가 다 저장되잖아요. 근데 똑같이 이름으로 했을 때도

이름에 대한 모든 데이터도 저장하고 그 다음에 전화번호를 쓸 때도 전화번호에 대한 모든 데이터도 저장하고 이런 식으로 확인을 보면은 어떤 학생 한 명의 데이터가 여기에도 저장이 되고 여기에도 저장해서 여기에도 저장해서 이런 식으로 중복해서 많이 저장되는 단점이거든요. 똑같은 데이터인데 한 번만 저장하면 되는데 학원에 대해서도 저장이 되고 이름에 대해서도 저장이 되고

전화번호에 대해서 저장되어 있고 이렇게 되면 비효율적이기 때문에 어떤 전략을 티냐 하면 학번일 때는 모든 데에들만 저장하는데 이름이나 전화번호에 내릴 때에는 모든 데에 대해서 저장하는 것이 아니라 여기에서 학번을 써야 되는 거예요. 이 이름은 학번이 뭐야 이 전화번호는 학번이 뭐야 라고 해서 전화번호에 들어가면 학번이라고 할 수가 있죠. 근데 모든 데에 대해서 다 알고 싶으면 이 전화번호는 학번을 알아와서

나와서 학번에 대해서 또 찾으면 돼요. 학번에 대해서 찾으면 이런 데이터를 더 낳을 수가 있습니다. 그래서 이 튜플레이터를 진짜로 이 리프 노드의 변경에 저장하고자 한다고 하면은 기본키일 때는 이것을 하지만 보조키, 기본키가 아닌 경우에는 모든 데이터를 저장하는 것이 아니라 기본키를 저장하게끔 해서 한 번 더 검색을 해야 되는 번거로움이 있어요.

-뉴얼서. -뉴얼서. -뉴얼서. -뉴얼서. -뉴얼서. -뉴얼서. -뉴얼서.

단단점이 있거든요. 첫 번째 전략이랑 두 번째 전략이 있는데 첫 번째 전략에 단점이라고 한다면 이게 다 하나하나가 디스크로 되어 있다고 했잖아요. 디스크를 해야 되는데 디스크를 읽어서 뭔가 퀵값을 얻어왔는데 또 프린터가 딴 데가 켜서 디스크를 또 읽어야 돼요. 이렇게 다 가서 읽어보려고 하면은

그래서 디스크에데이터가 늘어나면 단점이 되는데, 튜플 데이터를 저장했다고 한다면, 학번에 대한 데이터가 다 저장되어 있으니까 바로 읽어보면 되겠죠. 추가적인 디스크에데이터가 필요하지 않아요. 학번에 대해서는 바로 한번에 읽어볼 수가 있어요. 그래서 빠른데, 문제는 학번이 아니라 다른 보조인덱스가 사용됐을 경우에

전화번호로 학번으로 모든 데이터 찾고 두 번 일어나야 될 때인데 굉장히 느려지게 됩니다. 기본 키 인덱스일 때는 굉장히 빠른데 고조에 대해서는 굉장히 느려져요. 그래서 이런 단점이 있어요. SQL 서버랑 오라플 같은 경우에는 approach 1이나 2 선택해서 쓸 수가 있고요.

이것들은 어플 지원, 이것들은 어플 지원을 사용합니다. 장단점이 있는 거라서 상황에 따라서 선택해서 써야겠죠. 주키로 주로 공생이 일어난다 그러면 이게 더 유의한데 그렇지 않으면 이게 이루어야겠죠. B3와 B+3가 어떻게 다른지 나와있는데 B3 같은 경우에는

이럴 때는 인원 노드에 데이터가 저장이 안되는데, 밑줄은 인원 노드에도 데이터가 저장이 되요. 그래서, 공간을 좀 더 효율적으로 쓸 수가 있는데, 문제는 동신성 제어가 꽂혀 버렸습니다. 무슨 말인가 하면은,

삽입이나 삭제가 일어났을 때 B+tree는 데이터가 실제로 이 하단에만 존재하기 때문에 맨 밑에 와서 여기가 고쳐지고 있으면 여기에만 락이 오리거든요. 여기는 못보지만 다른 데다 볼 수가 있거든요. 그래서 다른 사람들은 이 티리드를 활용할 수가 있는데 이 B-tree 같은 경우는 3단에서 삽입이나 삭제가 일어나서 여기 데이터가 있기 때문에 여기가 락이 오를 수가 있어요.

그래서요. 락에 올리게 되면 상단부분을 못쓰게 되더라구요. 상의에 비해서 올리게 되면. 그래서 동의성 제거가 힘듭니다. 그래서 그 단점이 있기 때문에 b+3를 쓸구요. b+3는 리프늘드에만 저장이 되어 있고. 지워진 키가 리프늘드는 지워지지만 중간 유리에서 설아 있을 수 있다고 되는데. 이건 뒤에 외계에서 보시면은.

보시면은 예발되실거에요. B+Tree에 삽입 예제인데요. 삽입할 때 적당한 리프 노드를 찾아서 집어넣으면 되는데 장소만 있으면 넣으면 되고요. 라인 가득 찬다. 그럼 스피릿을 해줘야 돼요. 그래서 어떻게 일어나는지 한번 해보도록 하겠습니다. 이렇게 생긴 B+Tree가 있고요.

6을 집어넣을 거에요. 6은 3 다 크니까, 7 다 크니까. 3 다 크니까. 빈자리가 없어요. 빈자리가 없어서. 어쩔 수 없이 스프릿이 일어납니다. 그래서 2개로 늘어나고. 전체 아이템이 4개가 되니까 2개씩 나눠가죠. 5, 6, 5, 10. 이렇게 나눠가죠. 가리키는 데가 없죠. 가리키는 데가 없으니까. 가리키는 데는 만들기 위해서.

불을 올려야 합니다. 여기 값을 올려서 가르치는 겁니다. 어렵지 않죠? 팔을 넣고 싶다. 팔을 여기 오면 되겠죠? 사과 부 사이에 있으니까 팔을 넣으면 되겠죠? 그 다음은 다른 툴이에요. 두 번째 예제인데 17을 넣고 싶다. 17은 여기 오면 되겠죠? 17을 여기 오면 되겠죠?

이렇게 심리욕도 여기 들어오게 되는데 각이 찼어요. 이렇게 스플릿 해줘야 돼요. 스플릿해서 이제 3개, 2개로 나눠왔습니다. 여기 가리키는데 심리욕을 넣으려고 하다 보니까 각이 찼죠? 그래서 어쩔 수 없이 쟤도 스플릿이 일어나서 층이 하나 늘어나게 됩니다. 이렇게 들어가서 이렇게 삽입이 완료가 됩니다.

삽입 알고리즘은 자세하게 소위는 안되는데 대략적으로 어떻게 도착하는지 아시면 될 것 같고요. 자세한 것 자유구조 시간은 배우선 시크라고 생각하고 이 정도로 확보해 넘어가도록 하겠습니다. 지우는 것도 마찬가지인데 지우는 것도 적당한 곳을 찾아서 지울 수 있으면 지우고 지우는데 만약에 절반이 차지 않았다 한다면 옆에서 빌려와야 합니다.

- Yeah. - Yeah.

여기서 처리가 안됐다. 그러면 층이 줄 수 있는데 예제을 통해서 보시면 6을 지우게 된다. 80원에 6을 여기서 지우게 되는데 지우는 순간 절반 이상 안착이 되죠. 옆에서 빌려와요. 1,3에서는 빌려온 문제이기 때문에 9,3에서 빌려온 문제이기 때문에

그렇기 때문에 9, 12, 14에서 들어갑니다. 그런데 이제 문제가 되는 게 9보다 작은 애들만 와야 하는데 9가 들어와 있잖아요. 그래서 5기를 고쳐줘야 해요. 12로 고쳐주면 되겠죠. 두 번째 예정인데 15를 줄이고 싶다. 15를 줄이면 절반 이상 안착해서 17, 19, 20에 들어가야겠죠.

17을 빌려왔어요. 17을 붙여줘야겠죠. 19로 붙여줍니다. 19를 지우고 싶다. 19를 지우니까 문제가 생겼고 빌려올 데가 없어요. 빌려올 데가 없으면 머지게가 나뉩니다. 이렇게 합쳐져요. 이렇게 필요 없어졌는데 문제는 위에 있는 간이

절반이 다 안찼죠. 절반이 다 안찼기 때문에 여기다 빌려오려고 했는데 빌려올 수도 없고 밑에 있는 걸 떨궈서 이렇게 확해지게 됩니다. 이런 식으로 보기로 합니다. 여기서 보시면 식구를 지웠는데 밑에 있다는 식구를 지워졌지만 여기 살아있죠? 이렇게 살아있을 수도 있어요. 중간에

중간 이너노드에서는 사랑해 쳐도 되고 아무 문제 없습니다. 그래서 b+3의 3일까지 삭제에 대해서 알아봤는데 자료조 시간에 공부하시는 걸로 보충을 하시면 될 것 같고 요리는 잠시 확인 안하고 이렇게 진행된 값만 읽히시면 될 것 같습니다.

여태까지는 B+Trill은 키 하나에 대해서만 만져봤는데 여러 개의 키에 대해서 만져봤는데 B+Trill은 보카 및 대수도 만져봤는데 여기서부터는 월요일에 하도록 하겠습니다. 오 굉장히 빨간다. 월요일을 하도록 하겠습니다. 앞에서 공간장에 진도 마쳐야 해서 인정해보겠습니다.