Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Sign up for free
Menu
Search
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Features
All features
Private URLs
Password Protection
Custom URLS
Scheduled publishing
Remove Branding
Restrict embedding
Deck Collections
Notes
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Explore
Featured decks
Featured speakers
Programming
Technology
Storyboards
Pricing
Search
Sign in
Sign up for free
DB Tree Algorithms
Search
Sponsored
·
SiteGround - Reliable hosting with speed, security, and support you can count on.
→
Yunosuke Yamada
October 16, 2022
Programming
140
0
Share
Embed
Copy iframe code
Copy JS code
Copy link
Start on current slide
DB Tree Algorithms
Yunosuke Yamada
October 16, 2022
Transcript
19 slides
DBとアルゴリズム 2021/09/09 山田悠之介
Web の技術とアルゴリズム アルゴリズムの理論には純粋なパズル的な楽しさがある Web の技術ではプラクティカルな話が中心で理論の話は多くない (そんな事ないよって方の LT をお待ちしています) DB は理論の話が多く面白い
今回は DB にまつわるアルゴリズムのうち、木に関するものを紹介 2
流れ データ構造をいくつか紹介 BST B-tree LSM tree(主題) 時間があれば LSM tree における最適化をいくつか紹介
3
BST(二分探索木) 右部分木のノードは親より大きく、左部分木のノードは親より小さい 多くの言語で Map, Set の実装に使われる 4
BST(二分探索木) バランスしている時、読み込み・書き込み (INSERT, UPDATE, DELETE)がO(log N) 5
BST はディスクと相性が悪い バランシングが頻発する → ディスクの読み書きが増える ノードサイズとページサイズと合っていない 6
B-tree (B+ tree) ディスクに最適化された探索木 多くの RDBMS (MySQL, PostgreSQL など) のストレージエンジン
でインデックスとして用いられている 7
B-tree (B+ tree) ディスク最適化 各ノードの大きさをページサイズに合わせる バランシングも兄弟への分割・兄弟とのマージなので局所的 8
B-tree の向き・不向き 読み込み・書き込みともに だが、 書き込みが多いユースケースではボトルネックになる ミュータブルなので排他制御が必要 O(log N) 9
LSM tree 書き込みに最適化されたデータ構造 Cassandra などの NoSQL, Spanner などの分散 DB で用いられる
書き込みが 、読み込みが 書き込み時はメモリとログに書くだけにして、 重複を読み込み時に解決する ディスク上のコンポーネントはイミュータブルで、 ロックなしで読み書きできる O(1) O(N) 10
LSM tree 小さなメモリ上のコンポーネント (memtable) 大きなディスク上のコンポーネント(複数) からなる 11
LSM tree 全ての書き込みは memtable に適用される 耐久性を保証するためにログファイルが必要となる memtable はサイズが閾値になると,ディスク上に永続化される ディスク上のデータ構造は B-tree
が一般的 12
LSM tree フラッシュ後のテーブルの数を抑えるために定期的にマージする (コンパクション) コンパクションではマージされた結果を新しいファイルに書き出す (イミュータブル) 13
LSM tree の書き込みと読み込み 追加・更新は memtable に新たに key と value を追加するだけ
削除では memtable からデータレコードを削除するだけでは不十分 (ディスク上のコンポーネントが同じキーのデータレコードを 保持している可能性がある) value に特別な削除エントリ(墓石)を割り当てることで対応 読み込みでは複数のコンポーネントにアクセスし、 タイムスタンプを比較して最新の結果を返すようにする → どのコンポーネントにレコードがあるか知りたい 14
Leveled compaction レベル 0 はフラッシュされたテーブルがそのまま入る レベル 1 以降は上のレベルからマージされ、 key の範囲が各レベルで被らないようにすることで探索を最適化する
15
Bloom Filter 各レベルである key がどのテーブルの範囲にあるかはわかるが、 本当にそのテーブルにあるかは分からない Bloom filter という確率的データ構造がよく使われる 16
Bloom Filter 構築時: 要素の key に対して hash 値のビットを全て立てる (ビット配列は共有) 探索時:
hash 値のビットが全て立っていれば要素かもしれない、 そうでなければ要素ではない 17
まとめ B-tree は読み込み・書き込みともに優れたデータ構造 特殊なケースでは書き込みに特化した LSM tree が使われる LSM tree の読み取りを改善する最適化がいろいろある
18
参考資料 Database Internals 19
More Decks by Yunosuke Yamada
See All by Yunosuke Yamada
AI時代に成長するエンジニアに必要なスキルとは.pdf
yunosukey
0
330
Gemini CLIでもセキュアで堅牢な開発をしたい!
yunosukey
1
730
DevOps/MLOpsに学ぶエージェントの可観測性
yunosukey
1
1.3k
Agent Development Kitで作るマルチエージェントアプリケーション(AIAgent勉強会)
yunosukey
4
2k
Agent Development Kitで作るマルチエージェントアプリケーション(GCNT2025)
yunosukey
0
110
AIエージェントのオブザーバビリティについて
yunosukey
1
970
OpenTelemetry + LLM = OpenLLMetry!?
yunosukey
2
1.3k
クラウド開発環境Cloud Workstationsの紹介
yunosukey
0
510
フロントエンドオブザーバビリティ on Google Cloud
yunosukey
1
410
Other Decks in Programming
See All in Programming
React Native経験者が Flutterを30⽇間触って驚いたこと
3saito
0
200
Scalaの型でマルチテナントの認可を守る
nextbeatdev
0
160
クラウドゲーミングのパフォーマンス最適化に挑む / Cloud Gaming Performance Tuning
vivion
0
350
疎結合とは何か?ソフトウェア設計における結合バランスについて考える #phpcon_niigata
kajitack
2
320
自作Discord音声botをLambda MicroVMsに移行した話 / Migrating My Discord Voice Bot to Lambda MicroVMs
akihisaikeda
1
370
そのデザイントークン、Flutterでも同じ見た目になりますか?
nakamizu
0
430
AIが実装を担う時代の「技術設計」と「チームマネジメント」
kamina_zzz
2
280
Claude Code ハーネスDeep Dive – 君はどこまで制御する? -
takateeen_knj
6
6.1k
SODA - FACT BOOK(JP)
sodainc
1
40k
Materialが消えた日 〜真っ白なFlutterキャンバスにRenderObjectで絵を描く〜
umigishiaoi
0
170
Goコンパイラを作ってGoをもっと理解する / Build a Go compiler to better understand Go
ikura_hamu
0
130
AIコーディング時代のKotest ユニットテストから APIレベルの仕様固定化テストへ
ooga04
0
270
Featured
See All Featured
10 Git Anti Patterns You Should be Aware of
lemiorhan
PRO
659
62k
Reflections from 52 weeks, 52 projects
jeffersonlam
356
22k
The Art of Delivering Value - GDevCon NA Keynote
reverentgeek
16
2.2k
Raft: Consensus for Rubyists
vanstee
143
7.9k
Agile Leadership in an Agile Organization
kimpetersen
PRO
0
310
The SEO identity crisis: Don't let AI make you average
varn
0
630
GraphQLとの向き合い方2022年版
quramy
50
15k
Mind Mapping
helmedeiros
1
440
Ten Tips & Tricks for a 🌱 transition
stuffmc
1
290
Large-scale JavaScript Application Architecture
addyosmani
516
110k
Designing for Timeless Needs
cassininazir
1
570
Designing Experiences People Love
moore
143
24k