DB3: The Search Tree (B-Tree) Makes the Index Fast

Tham khảo: use-the-index-luke
Lưu ý: A B-tree is a balanced tree—not a binary tree.
Do các index leaf node đc lưu trữ theo thứ tự tùy ý - có nghĩa là vị trí các index leaf node này ở trên disk không trùng với vị trí logic (logical position)theo thứ tự index.
Nên cần 1 cấu trúc dữ liệu nữa là B-Tree -> The balanced search tree, để tìm kiếm nhanh hơn
Hình sau mô tả cấu trúc B-Tree

nhìn hình trên ta thây:
Mỗi branch node entry tương ứng với giá trị lớn nhất trong mỗi leaf node;
The next layer cũng tương tự. Việc này sẽ lặp đi lặp lại cho đến khi all keys fit into a single node, the root node.
1 khi index đc tạo thì database sẽ maintains 1 cách tự động. điều này dẫn đến mỗi lệnh: insert, delete, update sẽ tiêu tốn nhiều time
B-Tree Traversal

Hình trên mô tả 1 index fragment để biểu diễn tìm kiếm key “57”.
cây này sẽ duyệt từ root node, theo thứ tự tằng dần, đến khi >= 57 thì nhảy sang node gần hơn.
cứ lặp đi lặp lại như vậy cho đến leaf node
The B-tree enables the database to find a leaf node quickly.

thelam92