[12주차] B-트리

[ella-yschoi]

B-트리에 대해 알아보아용

[hanana1253]

요약

• 오늘은 condition nienzo로 대충 읽기만 해서 요약은 스킵

느낀점

• ㅎ... 조금 읽을만해졌더니 다시 이해가 안되는 부분이 많아진 B-트리
• 인상적인 특징으로는...
  • 항상 균형을 유지하고 모든 리프 노드는 루트 노드로부터 동일한 깊이에 있다
  • 언제나 루트가 아닌 각 내부 노드가 최소 반 이상 차 있도록 보장한다.
  • 트리가 균형을 많이 잃으면 트리 기반 구조의 이점을 잃기 때문에 구조를 지속적으로 재배치한다.

[ella-yschoi]

condition nienzo 한결님 여행 잘 다녀오셨나용

[ddongule]

콩디션 죠아져라 얍!

[hanana1253]

호잇 귀여운 응원 감사합니다
컨디션 난조라고 말하긴 했지만 그냥 "요약할정도로 열심히 읽기 너무 귀찮다" 정도라서 부끄럽군요
여행 재밌게 잘 다녀왔고 요새 회사일이 너무 빡세서 괴로와요 흑흑
오늘도 일해야해서 컴퓨터를 켰지만 하기 시러서 딴짓 중 후후

[yunseorim1116]

요약

코드가 많아서 이해하려면 몇 번 읽어야 할 것 같군요
이 파트를 읽으면 비트리를 이해할수 있을까? 했는데
여전히 아리송하고 어려웠네요
일이 많아..... 무엇에 우선순위를 둘지 감이 안잡히는 3월 2일 .....

[hanana1253]

건강에 우선순위를 두십시다 우리모두!!!

[ddongule]

🐝 tree..란 무엇인가.. 무엇일까?..
일단은 저도 현생이 babba서 요약 skip.. (마치 원래는 요약 항상 했던것처럼..)
읽었는데 한번 더 읽어야할 것 같아요^^..
핵간단 정리

• 비트리는 하나의 노드가 많은 자식을 가질 수 있는 균형트리 자료구조 - 대용량 데이터에서 성능을 보장
• 노드를 불러오는 횟수를 줄이기 위해 최적화되어있음
• 트리가 균형을 많이 잃지 않기 위해 구조를 지속적으로 재배치함
• 데이터를 빠르게 찾는데 도움을 줌 (..)

[hanana1253]

나중에 비트리만 한 번 더 읽기 모임 해야할듯..
근데 이 책 처음엔 쉬울것처럼 꼬셔놓고 비트리 갑자기 들이미는거 너무 물회하지 않나요?

[ella-yschoi]

요약

• 머릿속으로 그려가며 읽어야했던 이번 챕터..
• 핵심은 '균형'인 것 같아요.

[hanana1253]

연수님 요약 덕에 책보다 더 잘 이해하고 갑니다

[sunhpark42]

• 여전히 어려웠던 비트리
• 이거 데이터베이스 할 때 중요하게 다뤘던 기억이 남아있다.
• 로직의 복잡도를 높이는 대신 노드 접근 수를 줄이는 방식인데, 세상 기기가 발전해서 저장소 접근 비용이 줄어든다면 사용하지 않으려나 싶기도 하는 생각이랑 더 복잡한 구조가 생기려나 하는 생각도 드는 이번장이었다.

[ainochi-kor]

정리

• 데이터베이스 알고리즘에 쓰인다곤 들었는데, 뇌에서 정보 입력을 거부당해서 받아쓰기만 잔뜩 해버렸네요...

[hanana1253]

받아쓰기 잘 하셨군요 최고최고..

[thgr8ganzi]

정리

• 비트리 어려워요
• 비트리랑 이진트리라우헷갈린적이 있네요
• 비트리는 어떻게보면 트리형식으로 이루어진 해시함수 없은 해시테이블?

[sa02045]

• B-트리는 디스크 블록 단위 접근 특성을 잘 활용하는 알고리즘 정도로만 이해했습니당. 자세한 구현은 나중에 다시 봐야겠네요..

  • 데이터베이스, 파일 시스템에서 사용되는 알고리즘
  • 노드 크기가 디스크 블록 크기에 맞춰짐
  • 트리 높이가 낮음
  • 한번에 I/O로 많은 데이터를 처리함. 디스크 I/O 비용을 최소화하도록 설계됨

• 자식수 최대 M개 가짐(여러개)

• 항상 균형을 유지함

[iborymagic]

• 솔직히 아직도 잘 모르겠습니다 ㅋㅋ;
• 맨날 다시 읽어봐야겠습니다 하고 안읽는데 진짜 읽어봐야겠습니다 ㄹㅇ로

---

• B-트리?
  • 한 노드에 여러 개의 데이터를 저장하여 탐색 비용을 절약하는 트리
  • 균형이 유지됨
  • 모든 리프 노드는 같은 깊이를 가짐
  • 인덱싱 + 저장 -> 탐색 성능 최적화
• 탐색
  • 한 노드에서 여러 개의 키를 스캔
  • 목표보다 큰 키를 찾으면 해당 자식 노드로 이동하여 탐색 계속
• 키 삽입
  • 트리를 따라 내려가면서 삽입할 위치 찾음
  • 동일한 키가 있으면 데이터 갱신
  • 없으면 리프 노드에 추가
• 키 제거
  • 트리를 따라 내려가면서 삭제할 키 찾음
  • 키 제거 후, 균형이 깨지지 않도록 조정
  • 빈 루트 노드를 제외하면 항상 균형 유지
• B-트리의 중요성
  • 디스크 및 외부 저장 장치에서 데이터를 빠르게 찾기 위해 사용
  • 노드 내에서 많은 데이터를 저장하여 접근 횟수를 최소화
  • 자동으로 균형 유지하여 효율적인 데이터 검색 보장

[chloe-codes1]

• B-Tree 는 가장 널리 사용되는 index 구조라서 DB 와 연관지어 생각하며 읽었다
• B-Tree (or B+Tree)를 사용하는 DB
  • RDBMS
    • MySQL (InnoDB) – B+Tree
    • PostgreSQL – B-Tree
    • Oracle – B+Tree
  • NoSQL
    • MongoDB – B+Tree
    • SQLite – B-Tree
• 여기서 B+Tree는 모든 데이터를 리프 노드에만 저장하고, 내부 노드는 index 역할만 수행한다
  • B-Tree vs B+Tree
    • B-Tree
      • 내부 노드와 리프 노드에 데이터가 저장됨
      • 탐색 속도가 빠를 수도 있지만 범위 검색에는 불리함
    • B+Tree
      • 모든 데이터를 리프 노드에 저장하고 내부 노드는 인덱스 역할만 함
      • 범위 검색과 디스크 I/O 최적화에 유리
• key-value store나 log 기반 DB에서는 B-Tree 보다는 LSM-Tree를 많이 사용하는 것 같다
  • 쓰기 성능 극대화 & 디스크 I/O 줄이는 목적
    • B-Tree는 랜덤 쓰기가 많아서 LSM-Tree보다 쓰기 성능이 떨어짐
    • LSM-Tree는 순차 쓰기!
  • e.g. Cassandra, HBase

+
B-Tree에 관한 내용을 좀 더 알고 싶으시다면 데이터 중심 애프리케이션 설계 책의 03장: 저장소와 검색을 읽어보시는 것을 추천합니다~~

[hanana1253]

오... 좀더 알고 싶지만 알고 싶지 않고 읽고 싶지만 읽고 싶지 않은 모순적인 나! 그치만 꼭 참고할게요