B-tree và chỉ mục cơ sở dữ liệu

B-tree là gì?

• B-tree đóng vai trò nền tảng trong nhiều phần mềm, đặc biệt là các hệ quản trị cơ sở dữ liệu (DBMS)

• MySQL, Postgres, MongoDB, Dynamo... dựa vào B-tree để truy xuất dữ liệu hiệu quả thông qua chỉ mục

• Bài viết sẽ tìm hiểu cách B-tree và B+tree hoạt động, vì sao cơ sở dữ liệu dùng chúng cho chỉ mục, và vì sao dùng UUID làm khóa chính có thể là một ý tưởng tồi

• B-tree lưu các cặp dữ liệu được gọi là khóa và giá trị trong một cấu trúc mà lập trình viên gọi là giống cây

• B-tree gồm các nút (hình chữ nhật) và con trỏ con (các đường nối giữa các nút)

• Nút trên cùng được gọi là nút gốc, các nút ở tầng dưới cùng là nút lá, còn lại là nút bên trong

• Dưới đây là định nghĩa của B-tree:

  • Mỗi nút lưu N cặp khóa/giá trị (trong đó N lớn hơn 1 và nhỏ hơn hoặc bằng K)
  • Mỗi nút bên trong có ít nhất N/2 cặp khóa/giá trị (nút bên trong là nút không phải lá hay gốc)
  • Mỗi nút có N+1 nút con
  • Nút gốc có ít nhất một giá trị và hai nút con, trừ khi nó là nút duy nhất
  • Mọi nút lá đều ở cùng một mức

• Một đặc điểm cốt lõi khác của B-tree là tính sắp xếp. Các phần tử trong mỗi nút luôn được giữ theo thứ tự

• Nhờ đó có thể tìm kiếm khóa rất hiệu quả. Quá trình tìm kiếm bắt đầu từ nút gốc và:

  1. Kiểm tra xem khóa cần tìm có trong nút hay không
  2. Nếu không, xác định vị trí khóa sẽ được chèn vào nút nếu cần thêm mới
  3. Từ đó, đi theo con trỏ con xuống tầng tiếp theo và lặp lại quy trình

• Theo cách này, để tìm một khóa chỉ cần truy cập một nút ở mỗi tầng của cây

• B-tree được thiết kế đặc biệt để hoạt động tốt khi có rất nhiều dữ liệu và vẫn phải được lưu bền vững trên bộ nhớ dài hạn (đĩa). Lý do là mỗi nút dùng một số byte cố định

• Số lượng giá trị mỗi nút có thể lưu trong B-tree phụ thuộc vào số byte được cấp cho nút đó và số byte mà mỗi cặp khóa/giá trị tiêu thụ

B+tree (được tối ưu cho cơ sở dữ liệu)

• B+tree tương tự B-tree, nhưng có các thay đổi về quy tắc như sau:
  • Các cặp khóa/giá trị chỉ được lưu ở nút lá
  • Các nút không phải lá chỉ lưu khóa và con trỏ con liên quan
• Cách MySQL triển khai B+tree trong chỉ mục còn có thêm hai quy tắc riêng:
  • Các nút không phải lá lưu N con trỏ con thay vì N+1
  • Mọi nút còn bao gồm cả con trỏ "next" và "previous", để mỗi tầng của cây cũng có thể hoạt động như một danh sách liên kết kép
• Có hai lý do khiến B+tree phù hợp hơn với cơ sở dữ liệu:
  1. Nút bên trong không cần lưu giá trị nên có thể chứa nhiều khóa hơn trên mỗi nút. Điều này giúp giảm độ sâu của cây
  2. Mọi giá trị đều được lưu ở cùng một mức và có thể được duyệt theo thứ tự qua danh sách liên kết ở tầng dưới cùng

Cách MySQL dùng B+tree

• MySQL hỗ trợ nhiều storage engine, và engine được dùng phổ biến nhất là InnoDB, vốn phụ thuộc rất nhiều vào B+tree
• Trên thực tế, InnoDB phụ thuộc đến mức lưu toàn bộ dữ liệu bảng trong B+tree bằng cách dùng khóa chính của bảng làm khóa của cây
• Mỗi khi tạo một bảng InnoDB mới, bạn cần chỉ định khóa chính
• MySQL sẽ tạo một B+tree cho mỗi bảng mới; giá trị được đặt làm khóa chính sẽ là khóa của cây. Giá trị là các cột còn lại của từng hàng và chỉ được lưu ở các nút lá
• Kích thước mỗi nút trong B+tree này mặc định được đặt là 16k
• Mỗi khi MySQL cần truy cập một mẩu dữ liệu (khóa, giá trị...), nó sẽ nạp toàn bộ trang liên quan (nút B+tree) từ đĩa, ngay cả khi không cần các khóa hay giá trị khác trong trang đó
• Việc tạo chỉ mục phụ trên bảng InnoDB cũng rất phổ biến. Với mỗi chỉ mục phụ, một B+tree bền vững bổ sung sẽ được tạo ra; khóa là cột mà bạn chọn để lập chỉ mục, còn giá trị là khóa chính của hàng tương ứng

Chọn khóa chính: chèn dữ liệu

• Vì cách dữ liệu bảng được sắp xếp trong B+tree phụ thuộc vào khóa bạn chọn, nên việc chọn PRIMARY KEY ảnh hưởng đến bố cục đĩa của toàn bộ dữ liệu trong bảng
• Hai lựa chọn thường gặp cho khóa chính là:
  • dãy số nguyên (BIGINT UNSIGNED AUTO_INCREMENT...)
  • UUID (có nhiều phiên bản)
• Nếu dùng khóa chính UUIDv4, khi chèn dữ liệu sẽ có các hệ quả sau:
  1. Không thể dự đoán trước nút nào sẽ được truy cập để chèn
  2. Không thể dự đoán trước nút lá đích cho việc chèn
  3. Giá trị trong các lá sẽ không được sắp theo thứ tự
• Vấn đề số 1 và 2 xảy ra vì trong quá trình chèn nhiều lần, phải truy cập nhiều nút (trang) khác nhau trong cây. Việc đọc và ghi quá mức này dẫn đến suy giảm hiệu năng
• Nếu dùng BIGINT UNSIGNED AUTO_INCREMENT làm khóa chính:
  1. Khi chèn giá trị mới, luôn đi theo nhánh ngoài cùng bên phải
  2. Lá chỉ được thêm ở phía bên phải của cây
  3. Ở mức lá, dữ liệu được sắp theo đúng thứ tự đã chèn
• Nhờ 1 và 2, nhiều thao tác chèn diễn ra tuần tự sẽ lặp lại cùng một đường đi qua các trang, nên giảm số lượng yêu cầu I/O khi chèn nhiều cặp khóa/giá trị

Chọn khóa chính: đọc dữ liệu theo thứ tự

• Việc truy xuất dữ liệu theo thứ tự thời gian là rất phổ biến trong cơ sở dữ liệu
• Nếu dùng UUIDv4 làm khóa chính, chuỗi giá trị trong kết quả truy vấn sẽ bị phân tán trên nhiều nút lá không liền kề
• Khi tìm các giá trị được chèn tuần tự, mọi trang chứa kết quả tìm kiếm sẽ nằm sát nhau. Khi truy xuất nhiều hàng, thậm chí tất cả có thể cùng nằm trên một trang duy nhất và liền kề nhau
• Với kiểu truy vấn như vậy, dùng khóa chính tuần tự có thể làm giảm số trang cần đọc

Chọn khóa chính: kích thước

• Kích thước khóa chính cũng là một yếu tố quan trọng. Khóa chính luôn phải:
  1. đủ lớn để không bị cạn kiệt
  2. đủ nhỏ để không tiêu tốn quá nhiều dung lượng lưu trữ
• Với dãy số nguyên, các bảng nhỏ hơn có thể dùng MEDIUMINT (16 triệu giá trị duy nhất) hoặc INT (4 tỷ giá trị duy nhất)
• Với bảng lớn, có thể dùng BIGINT để an toàn (khoảng 18 tỷ tỷ giá trị khả dụng). BIGINT là 64-bit (8 byte)
• UUID thường là 128-bit (16 byte), tức gấp đôi kiểu số nguyên lớn nhất của MySQL
• Vì các nút B+tree có kích thước cố định, dùng BIGINT sẽ chứa được nhiều khóa trên mỗi nút hơn so với UUID. Điều này dẫn đến cây nông hơn và tra cứu nhanh hơn

B+tree, page và InnoDB

• Một trong những ưu điểm lớn của B+tree là có thể đặt kích thước nút theo ý muốn
• Trong InnoDB, các nút B+tree thường được đặt bằng kích thước page của InnoDB, tức 16k
• Trong quá trình xử lý truy vấn (và vì thế là duyệt B+tree), InnoDB không đọc từng hàng và cột riêng lẻ từ đĩa. Mỗi khi cần truy cập một mẩu dữ liệu, nó sẽ nạp toàn bộ page liên quan từ đĩa
• Để giảm tác động này, InnoDB có một số kỹ thuật, trong đó quan trọng nhất là buffer pool. Buffer pool là bộ nhớ đệm trong RAM cho các page của InnoDB, nằm giữa các page trên đĩa và quá trình thực thi truy vấn của MySQL
• Khi MySQL cần đọc một page, nó sẽ kiểm tra trước xem page đó đã có trong buffer pool chưa. Nếu có, nó đọc từ đó và bỏ qua thao tác I/O đĩa. Nếu chưa có, nó sẽ tìm page trên đĩa, thêm vào buffer pool rồi tiếp tục thực thi truy vấn
• Buffer pool cải thiện hiệu năng truy vấn một cách rất lớn. Nếu không có buffer pool, hệ thống sẽ phải thực hiện nhiều thao tác I/O đĩa hơn rất nhiều để xử lý workload truy vấn

Một số tình huống khác

• Ở đây chủ yếu tập trung so sánh khóa tuần tự với khóa ngẫu nhiên/UUID, nhưng các nguyên tắc này vẫn là những điều hữu ích cần ghi nhớ bất kể bạn đang cân nhắc loại khóa chính hay khóa phụ nào
• Ví dụ, bạn có thể cân nhắc dùng dấu thời gian user.created_at làm khóa chỉ mục; nó có các đặc tính tương tự số nguyên tuần tự. Trừ khi chèn dữ liệu lịch sử, việc chèn thường sẽ luôn đi theo nhánh ngoài cùng bên phải
• Ngược lại, một chuỗi như user.email_address có đặc tính giống khóa ngẫu nhiên hơn. Người dùng không tạo tài khoản theo thứ tự chữ cái của email, nên việc chèn sẽ diễn ra rải khắp B+tree

Kết luận

• Bài viết đã đề cập khá nhiều về B+tree, chỉ mục và việc chọn khóa chính
• Nhìn bề ngoài thì có vẻ đơn giản, nhưng để khai thác tối đa hiệu năng của cơ sở dữ liệu, vẫn có những khác biệt tinh tế cần cân nhắc
• Để thử nghiệm thêm, hãy ghé thăm trang web B+tree tương tác

[GN⁺]

Ý kiến Hacker News

• Duy trì wiki hữu ích bằng cách áp dụng chiến lược quản lý như B-Tree

  • Khi trang đích trở nên quá dài, chuyển các liên kết và đoạn văn sang các trang con
  • Chuyển các liên kết cũ và tương tự sang các trang cùng cấp phù hợp với chủ đề
  • Cuối cùng, các tài liệu cũ sẽ được đẩy xuống ba cấp dưới trang đích
  • Tài liệu hóa cuối cùng quy về bài toán tìm kiếm
  • Đây là một cách tốt để có một buổi chiều thứ Sáu làm việc hiệu quả

• Tôi đã tìm thứ như thế này từ rất lâu rồi, một bài viết tuyệt vời

  • Ước gì có thêm một phần về chỉ mục tổng hợp

• Cảm ơn vì các hình minh họa tuyệt vời

  • Tôi từng làm việc trên hỗ trợ lập chỉ mục BTree+ chạy trên Aerospike
  • Việc loại bỏ các khóa hết hạn khỏi BTree+ là một thách thức
  • Chúng tôi quyết định chỉ hợp nhất một nhánh ở một cấp trong nút lá anh em đầu tiên
  • Chúng tôi thêm sharding lên trên BTree+ để tăng tốc độ và giảm tranh chấp khóa
  • Trong quá trình dọn dẹp, BTree+ có thể trở nên mất cân bằng
  • Chúng tôi cung cấp tính năng xây dựng lại chỉ mục để tránh thêm công việc dọn dẹp

• Trên Firefox di động, cửa sổ cookie không hoạt động

  • Nên cho người dùng có thể thiết lập điều đó trong trình duyệt

• Không nên dùng cột UUID làm khóa chính

  • Phải sao chép một số nguyên 128 bit vào mọi khía cạnh của quan hệ
  • Trong đa số trường hợp nó hoàn toàn ngẫu nhiên
  • Nên dùng PK bigserial (64 bit) cho các quan hệ bảng nội bộ, và dùng UUID (128 bit) cho định danh ở cấp ứng dụng cùng các khóa tự nhiên
  • Cơ sở dữ liệu sẽ "hạnh phúc" hơn rất nhiều

• Đây là tài liệu giảng dạy rất tốt

  • Những bản demo tương tác như thế này giúp ích rất nhiều

• Nếu khối đĩa và nút B-Tree đều là 16k, còn khóa, giá trị và con trỏ con đều là 8 bit, thì có thể lưu 682 cặp khóa/giá trị và 683 con trỏ con trên mỗi nút

  • Một cây ba cấp có thể lưu hơn 300 triệu cặp khóa/giá trị
  • Mỗi phần tử phải là 8 byte

• Bài viết rất hay

  • Việc InnoDB lưu dữ liệu ngay trong chính B-tree được gọi là chỉ mục cụm
  • MyISAM là chỉ mục không cụm
  • Oracle và những hệ khác cho phép lựa chọn

• Có người hỏi v0, v1, ...v10 trong biểu đồ có nghĩa là gì

  • Họ tự hỏi liệu nó có nghĩa là các trang khác nhau hay không

• Một hình dung tương tác rất đẹp

  • Xét về giáo dục và phổ cập, đây là đẳng cấp hàng đầu