[일반] b+트리가 왜 빠르다는거임?

[빛돌이(58.233)]

쏠리는거 방지한다고 이런짓 해놓은거 같은데 구조보면 되게 더럽지 않아요? 진짜 빨라여? 그냥 이진트리같은거보다?

[옥토끼(moonrabbit2)]

그게뭔데 - dc App

[익명(175.223)]

최악은 피할수있잖아

[시아닌(kimjg1119)]

적어도 편향은 없으니까

[시아닌(kimjg1119)]

근데 왜 프갤 말고 ps갤에 물어보냐

[빛돌이(58.233)]

알고리즘이라 여쭤봤는데 여기가 아닌가요 ㅠ

[0xrgb(0xrgb)]

그냥 이진트리보다 빠른 이유로 편향을 들면 안되지... 캐시 히트율때문에 빠른거임

[0xrgb(0xrgb)]

그래서 데이터베이스나 하드디스크 자료 저장하는 건 B 트리로 함

[빛돌이(58.233)]

b+가 아니라 b트리로?

[0xrgb(0xrgb)]

ㅈㅅ B+ 이었네

[0xrgb(0xrgb)]

B 트리도 자주 쓰이고 이거 계량판이 B+이라 더 나중에 만들어진 시스템에서는 B+도 쓰임 (e.g. XFS)

[codesafer(codesafer)]

흠 B트리랑 이진트리는 성능비교의 대상이 아님. B+ 트리는 B 트리에 순차 탐색이 가능토록 leaf node 들을 linked list 처럼 연결시킨것 뿐

[codesafer(codesafer)]

leaf 들만 정렬/링크 된 상태기 때문에 상위 노드들은 키만 갖고 있게 구성한 것이고, 키만 모아두면 캐시에 놓일 가능성이 높다는 것이지

[codesafer(codesafer)]

그냥 이진트리는 편향성이 있을 수 있고, 그 말은 complete tree 가 아닐 수 있다는 것이고, B 트리는 balanced 라 불리는 만큼 ( boeing 의 의미도 있지만 ) 보다 편향성이 적은건 맞음. 실제 구현에선 삽입 삭제 비용에 대한 고려와 - 이것때문에 약간의 공간낭비가 발생할 수 있음 -, 하나의 노드에 여러개의 entity 가 있을 수 있다는 점에서 차이를 보이는 것.

[codesafer(codesafer)]

이를 위해 구조가 복잡해지는건 어쩔수 없는데 더러운건 아님. ( 코드는 구현체에 따라 더러워질 수 있음 ). indexed access method ( IAM ) => B tree, indexed sequenntial access method ( ISAM ) => B+ tree, 라고 보면됨. ISAM 라이브러리들이 있는데, 이건 흔히 B+ tree 를 확장한 구현체라고 보면되고, 거기서 파일시스템과 강한 결합을 하게 되면 흔히 DBMS 가 되는 것. 물론 다중 접근 문제나 transaction recovery 이슈등이 포함되면 더 복잡한 DBMS 들이 되는 것.

[codesafer(codesafer)]

sequential 꾸엑 오타다.

[codesafer(codesafer)]

물론 DBMS 관련 수업을 듣게 되면 알겠지만 DBMS는 파일시스템 뿐만 아니라 관계형( 필드 / 레코드 )이니 객체지향이니, 처럼 어떤식의 데이타를 핸들링할 것인지 대상에 대한 구체화도 포함됨. 접근 방법 또한 API 형태든 SQL 처럼 스크립트를 거치는 것이든 여러가지로 나뉘게 되지.

[codesafer(codesafer)]

정렬된 트리 구조에서의 삭제는 비용이 무척 큰 편이기 때문에, 구현이 다소 복잡해질 수 밖에 없지. 그래서 tomb stone 같은걸 세운다든지 해서 공간을 잠시 희생하는 것.

[빛돌이(58.233)]

코세님하고 갤매님 감사요