geeknews를 보다가 B+tree 이해에 도움되는 글을 읽어서 공유해봅니다. B+tree에 대해서 자세히 알지는 않아서 저장해뒀다가 이제야 읽어봤는데요. 작동 방식을 interactive한 방식의 애니메이션으로 표현해줘서 이해가 잘 됐습니다.

작동 방식 뿐만 아니라, MySQL(특히 InnoDB)에서는 B+tree가 어떻게 활용되는지, PK로 UUID 대신 Integer sequence(e.g. bigint auto increment)를 쓸 때 장점이 뭔지, 연속적인 키가 B+tree에서 동작할 때 Buffer Pool와 만나면 왜 효과적인지를 알 수 있습니다.

---

이해한 대로 적어보는 간단 요약

• B+Tree

  • B-Tree 와 다르게 leaf 노드에만 key-value를 저장함

  • Non-leaf에는 key 와 자식 포인터만 저장

  • MySQL 추가 조건

    • Non-leaf 가 N개의 자식 포인터를 가지고 있음

    • next, previous 포인터가 있어서 각 레벨에서 이중연결리스트처럼 동작할 수 있음

• PK로 UUID

  • UUIDv4는 mostly-random 128 bit interger

  • b+tree 에 UUID 키를 추가할때 어느 노드에 추가될지 예측할 수 없음

  • 그래서 여러 노드를 탐색해서 insert 위치를 찾아야함

• PK로 Integer sequence(e.g. bigint auto increment)

  • 값을 추가할 때 항상 오른쪽(큰 값) 경로로 가면 됨. Leaf는 오른쪽에 추가되고 데이터는 삽입 시점을 기준으로 정렬됨

  • 많은 Insert가 있을 때 이전에 방문한 경로(노드, 페이지)를 다시 방문하기 때문에 I/O 요청을 많이 하지 않을 수 있음

• PK choice

  • 입력된 시간 기준으로 범위 검색하는 경우, sequence는 검색된 노드가 나란히 놓여지는데(순차로 넣었으니까) 반해 uuid는 여러 페이지를 봐야함(여기저기 퍼져있으니까)

  • integer sequence가 노드당 더 많은 키를 넣을 수 있음 (UUID는 일반적으로 16바이트, BIGINT는 8바이트) -> 트리가 얕아지고 조회속도가 빨라짐

• buffer pool

  • b+tree는 노드 크기를 원하는대로 설정할 수 있음. 일반적으로 InnoDB 페이지 크기인 16k로 설정됨

  • 쿼리 실행할 때 InnoDB는 row 단위로 읽는게 아니라 disk에서 전체 페이지를 읽어서 buffer pool에 저장함. buffer pool에 필요한 페이지가 없으면 disk I/O가 발생함

  • 그래서 이전에 방문한 노드(페이지)를 재활용할 수 있으면 buffer pool load&eviction이 줄어들어서 효과적임

https://planetscale.com/blog/btrees-and-database-indexes