B+Trees and why I love them, part I - Ayende @ Rahien

One of the things that I enjoy about learning new things is the way it changes the way I look at the stuff that I already knows. Reading the LMDB codebase, and implementing a persistent B+Tree has given me a new depth of understanding about how relational databases (and Esent, too), work. I am going to go back to level zero and assume that you have never heard about this. You probably know what a

[tgk]

output_2.jpgはsequential insertによるB+treeの成長の様子。それまでのroot nodeはブランチになり、新規ページが新たなroot nodeになる。だから左右のバランスが崩れない