B Tree và database index

B Tree là gì

B Tree là 1 cấu trúc dữ liệu được sử dụng rất nhiều trong Database, đặc biệt là RDBMS.

Nó là 1 cấu trúc dạng cây, do đó nó sẽ có nút gốc (root node), nút lá (leaf node) và các nút trong (internal node). Mỗi nút có 1 cặp key-value k-v

B Tree bậc K cần thỏa mãn các đặc điểm:

• Mỗi node chứa N cặp k-v, với N > 1 và N <= K (tối đa K cặp k-v)

• Mỗi internal node chứa ít nhất N/2 cặp k-v

• Mỗi node có N + 1 pointer trỏ đến node con

• Tất cả node lá phải cùng bậc (cây cân bằng)

Mỗi đặc điểm quan trọng của B Tree đó là tính thứ tự:

• Các phần tử trong mỗi node được sắp xếp theo thứ tự

• Node con bên trái của một key chỉ chứa các key nhỏ hơn

• Node con bên phải của 1 key chứa các key lớn hơn

B Tree

B-tree đặc biệt phù hợp với việc lưu trữ và tìm kiếm dữ liệu lớn trên ổ đĩa vì:

• Mỗi node có kích thước cố định, thường được lưu trữ dưới dạng block với kích thước 4k, 8k, 16k, 32k

• Với node 16KB có thể chứa tới 682 cặp key/value với giả định một node có tối đa 3 cặp k-v và pointer tới 4 node con cùng k, v, và pointer có kích thước 8 bit

• Một cây 3 tầng có thể lưu trữ hơn 300 triệu cặp key/value (682 x 682 x 682), một con số khổng lồ.

• Việc tìm kiếm rất hiệu quả vì chỉ cần duyệt 1 node ở mỗi tầng

B+ Tree là gì

B+ Tree là 1 phiên bản của B Tree nhưng có cải tiến một chút.

• k-v chỉ được lưu ở leaf node

• các node còn lại chỉ lưu giá trị k

Với MySQL, B+ Tree có thêm 2 đặc điểm:

• internal node lưu N pointer con thay vì N + 1 pointer

• các node cùng tầng với nhau sẽ liên kết với nhau tạo thành 1 liên kết đôi (Doubly-Linked List)

B+ Tree

B+ Tree phù hợp với database ở chỗ

• Các internal node ko cần thiết phải lưu cả cặp k-v, giúp giảm dung lượng lưu trữ

• Việc liên kết các node với nhau giúp cho việc duyệt cây rất nhanh, chẳng hạn sắp xếp, hay lấy top K phần tử.

Cách MySQL sử dụng B+ Tree

• InnoDB engine sử dụng B+ Tree để lưu dữ liệu, đặc biệt, nó lưu bảng theo dạng index với key là khóa chính (PK), cái mà ta hay gọi là Clustered Index. Đối với PostgreSQL thì nó không lưu bảng thành Clustered Index mà dùng kiến trúc khác (sẽ nói ở bài sau).

B+ Tree trong MySQL

• Khi insert 1 phần tử với Id tự tăng thì giá trị đó tự động được thêm vào node bên phải ngoài cùng của cây.

• Giả sử ta tạo index có tên index_email cho cột Email của table (UserId, Email) thì các internal node sẽ có key là giá trị email, các node là là cặp k-v với k là email và v là UserId của bản ghi. Khi tìm kiếm dựa trên email, db sẽ tìm trên index_email trước để có UserId rồi tìm tiếp UserId dựa trên bảng chính.

• Càng ít block được quét, câu query càng nhanh.

Điều gì xảy ra nếu ta chọn PK là GUID

• 1 điểm đặc biệt của GUID đó chính là tính ngẫu nhiên, tức là Id của chúng ta không có tính thứ tự khi được thêm vào. Điều này đặc biệt tốn thời gian vì khi add key ngẫu nhiên, db phải build lại cây để cân bằng, db sẽ không thể đoán trước được là giá trị mới thêm vào sẽ được add vào nốt nào.

• Đối với id được add tăng dần, db luôn biết được rằng giá trị được add sẽ nằm ở node cuối cùng và công sức để cân bằng cây là rất ít, chỉ cần cập nhật node cuối là xong

• 1 điều quan trọng khác là GUID có dung lượng lớn, tận 128 bit vì thế db phải lưu trữ nhiều hơn. với PK là Bigint (64 bit), khoảng 2^20 giá trị

Buffer pool

• Một điều quan trọng khác đó là ở mỗi DB đều có buffer pool. Đây chính là bộ nhớ đệm giúp db truy xuất dữ liệu nhanh chóng thay vì phải truy cập vào đĩa.

• Kiến trúc dạng cây, đặc biệt với mỗi node là 1 page/block thì buffer pool sẽ cache theo node. Giả sử có trường hợp page của bạn chỉ có 1 bản ghi thì buffer pool sẽ phải cache cả page/block đó nên vì vậy phải thiết kế làm sao mà số page/block được cache là ít nhất có thể.