CFSDN nhấn mạnh vào việc tạo ra giá trị thông qua mã nguồn mở. Chúng tôi cam kết xây dựng một nền tảng chia sẻ tài nguyên để mọi người làm CNTT có thể tìm thấy thế giới tuyệt vời của riêng mình tại đây.

Bài đăng trên blog CFSDN này Tại sao chỉ mục cơ sở dữ liệu MySQL chọn sử dụng cây B+? được tác giả thu thập và sắp xếp. Nếu bạn quan tâm đến bài viết này, hãy nhớ thích nó.

Trước khi phân tích sâu hơn về lý do tại sao MySQL database index chọn sử dụng cây B+, tôi tin rằng nhiều bạn vẫn còn hơi mơ hồ về cây trong cấu trúc dữ liệu, vì vậy chúng ta sẽ cùng tìm hiểu quá trình tiến hóa của cây từng bước từ nông đến sâu, sau đó giới thiệu từng bước về cây B và lý do tại sao MySQL database index chọn sử dụng cây B+! .

Những người đã nghiên cứu cấu trúc dữ liệu thường có một số kiến ​​thức về các loại cây cơ bản nhất, vì vậy chúng ta sẽ bắt đầu với cây tìm kiếm nhị phân, gần với chủ đề của chúng ta hơn.

1. Cây tìm kiếm nhị phân.

(1) Giới thiệu về cây nhị phân:

Cây tìm kiếm nhị phân còn được gọi là cây tìm kiếm nhị phân có thứ tự. Nó thỏa mãn các tính chất chung của cây tìm kiếm nhị phân, nghĩa là một cây rỗng có các tính chất sau:

1. Nếu cây con bên trái của bất kỳ nút nào không rỗng, giá trị của cây con bên trái sẽ nhỏ hơn giá trị của nút gốc; .

2. Nếu cây con bên phải của bất kỳ nút nào không rỗng, giá trị của cây con bên phải lớn hơn giá trị của nút gốc; .

3. Các cây con bên trái và bên phải của bất kỳ nút nào cũng là cây tìm kiếm nhị phân; .

4. Không có nút nào có giá trị khóa bằng nhau; .

Hình trên là một cây tìm kiếm nhị phân thông thường. Theo phương pháp duyệt theo thứ tự, đầu ra có thể được sắp xếp từ nhỏ đến lớn: 2, 3, 5, 6, 7, 8.

Để tìm kiếm cây nhị phân ở trên, ví dụ, để tìm kiếm một bản ghi có giá trị khóa là 5, trước tiên hãy tìm gốc có giá trị khóa là 6. 6 lớn hơn 5, vì vậy hãy tìm kiếm cây con bên trái của 6 và tìm 3. Vì 5 lớn hơn 3, hãy tìm kiếm cây con bên phải của nó. Tổng cộng có 3 lần tìm kiếm được thực hiện. Nếu bạn tìm kiếm cùng một yêu cầu ba lần theo thứ tự 2, 3, 5, 6, 7, 8. Sử dụng phương pháp tương tự để tìm kiếm bản ghi có giá trị khóa là 8. Lần này cần 3 lần tìm kiếm, trong khi tìm kiếm tuần tự cần 6 lần tìm kiếm. Tính số lần tìm kiếm trung bình, ta có: số lần tìm kiếm trung bình cho tìm kiếm tuần tự là (1+2+3+4+5+6)/6 = 3,3 lần và số lần tìm kiếm trung bình cho cây tìm kiếm nhị phân là (3+3+3+2+2+1)/6 = 2,3 lần. Tốc độ tìm kiếm trung bình của cây tìm kiếm nhị phân nhanh hơn tốc độ tìm kiếm tuần tự.

(2) Hạn chế và ứng dụng.

Cây tìm kiếm nhị phân được tạo thành từ n nút một cách ngẫu nhiên, do đó trong một số trường hợp, cây tìm kiếm nhị phân sẽ thoái hóa thành chuỗi tuyến tính với n nút. Như hình dưới đây:

Hãy xem hình ảnh trên. Nếu nút gốc của chúng ta là số nhỏ nhất hoặc lớn nhất, thì cây tìm kiếm nhị phân sẽ hoàn toàn thoái hóa thành cấu trúc tuyến tính. Số lần tìm kiếm trung bình trong hình trên là (1+2+3+4+5+5)/6=3,16 lần, tương tự như tìm kiếm tuần tự. Rõ ràng, hiệu quả truy vấn của cây nhị phân này rất thấp. Do đó, nếu bạn muốn xây dựng một cây tìm kiếm nhị phân có hiệu suất tối đa, bạn cần cây nhị phân này phải cân bằng (sự cân bằng ở đây có thể thấy từ một đặc điểm quan trọng là chiều cao của cây này lớn hơn chiều cao của đầu vào trước đó, không cân bằng trong trường hợp các nút giống nhau), dẫn đến một định nghĩa mới - cây nhị phân cân bằng AVL.

2. Cây AVL.

(1) Giới thiệu.

Cây AVL là cây tìm kiếm nhị phân có điều kiện cân bằng. Nó thường sử dụng chênh lệch hệ số cân bằng để xác định xem nó có cân bằng hay không và đạt được sự cân bằng thông qua phép quay. Chiều cao của cây con bên trái và bên phải không vượt quá 1. So với cây đỏ-đen, đây là cây nhị phân cân bằng nghiêm ngặt và điều kiện cân bằng phải được đáp ứng (chênh lệch chiều cao của cây con bên trái và bên phải của tất cả các nút không vượt quá 1). Bất kể chúng ta thực hiện thao tác chèn hay xóa, miễn là các điều kiện trên không được đáp ứng, chúng ta phải duy trì sự cân bằng thông qua phép quay, và phép quay rất tốn thời gian. Từ đó chúng ta có thể biết rằng cây AVL phù hợp với các tình huống mà số lượng phép chèn và xóa tương đối ít, nhưng có nhiều tìm kiếm.

Từ hình trên là một cây nhị phân cân bằng bình thường. Từ hình ảnh này, chúng ta có thể thấy rằng sự khác biệt về hệ số cân bằng giữa các cây con bên trái và bên phải của bất kỳ nút nào sẽ không lớn hơn 1.

(2) Hạn chế.

Vì chi phí duy trì mức độ cân bằng cao này lớn hơn mức tăng hiệu quả thu được từ nó nên không có nhiều ứng dụng thực tế. Nhiều nơi sử dụng cây đỏ-đen theo đuổi sự cân bằng cục bộ hơn là sự cân bằng tổng thể rất nghiêm ngặt. Tất nhiên, nếu kịch bản ứng dụng không yêu cầu chèn và xóa thường xuyên mà chỉ có yêu cầu cao về tìm kiếm thì AVL vẫn tốt hơn cây đỏ đen.

(3) Ứng dụng.

1. Có mặt rộng rãi trong nhân Windows NT; .

3. Cây đỏ đen.

(1) Giới thiệu.

Cây tìm kiếm nhị phân, nhưng có thêm một bit tại mỗi nút để biểu diễn màu của nút đó, có thể là đỏ hoặc đen. Bằng cách hạn chế cách tô màu các nút trên bất kỳ đường dẫn nào từ gốc đến lá, cây đỏ đen đảm bảo không có đường dẫn nào dài gấp đôi bất kỳ đường dẫn nào khác. Đây là cây nhị phân cân bằng yếu (vì nó cân bằng, có thể suy ra rằng trong cùng điều kiện nút, chiều cao của cây AVL thấp hơn chiều cao của cây đỏ đen). So với cây AVL nghiêm ngặt, thời gian quay của nó giảm đi, vì vậy khi có nhiều thao tác tìm kiếm, chèn và xóa, chúng ta sử dụng cây đỏ đen.

(2) Thiên nhiên.

1. Mỗi nút có màu đỏ hoặc đen; .

 2. Nút gốc có màu đen; .

3. Mỗi nút lá (nút lá là con trỏ NULL hoặc nút NULL ở cuối cây) có màu đen; .

4. Nếu một nút có màu đỏ thì cả hai nút con của nó đều có màu đen; .

5. Đối với bất kỳ nút nào, mỗi đường dẫn đến con trỏ NULL của cây điểm lá đều chứa cùng số lượng nút đen;

6. Mỗi đường dẫn đều chứa các nút đen giống nhau; .

(3) Ứng dụng.

1. Được sử dụng rộng rãi trong C++ STL, Map và Set đều được triển khai bằng cách sử dụng cây đỏ-đen; .

2. Trình lập lịch quy trình Linux nổi tiếng Completely Fair Scheduler sử dụng cây đỏ đen để quản lý khối điều khiển quy trình. Vùng bộ nhớ ảo của quy trình được lưu trữ trong cây đỏ đen. Mỗi vùng địa chỉ ảo tương ứng với một nút của cây đỏ đen. Con trỏ bên trái trỏ đến vùng lưu trữ ảo địa chỉ liền kề và con trỏ bên phải trỏ đến không gian địa chỉ ảo địa chỉ cao liền kề.

3. Việc triển khai ghép kênh IO epoll sử dụng tổ chức cây đỏ-đen để quản lý sockfd nhằm hỗ trợ thêm, xóa, sửa đổi và truy vấn nhanh chóng; .

4. Nginx sử dụng cây đỏ-đen để quản lý bộ đếm thời gian. Vì cây đỏ-đen được sắp xếp, bộ đếm thời gian có khoảng cách nhỏ nhất đến bộ đếm thời gian hiện tại có thể nhanh chóng có được;

5. Triển khai TreeMap trong Java;

4. Cây B/B+.

Nói đến ba loại cây trên: cây tìm kiếm nhị phân, AVL và cây đỏ đen, có vẻ như chúng ta vẫn chưa đề cập đến lý do tại sao MySQL sử dụng cây B+ làm triển khai chỉ mục. Đừng lo lắng, trước tiên chúng ta hãy thảo luận về cây B là gì.

(1) Giới thiệu.

Dữ liệu của chúng tôi trong MySQL thường được lưu trữ trên đĩa. Khi đọc dữ liệu, phải có thao tác để truy cập đĩa. Có hai bộ phận chuyển động cơ học trong đĩa, đó là chuyển động quay của đĩa và chuyển động của cánh tay từ. Tốc độ quay của đĩa là số vòng quay mỗi phút được đề cập trên thị trường, trong khi chuyển động của đĩa là khi đĩa quay đến vị trí đã chỉ định và di chuyển cánh tay từ để bắt đầu đọc và ghi dữ liệu. Sau đó là quá trình định vị khối trên đĩa và việc định vị là một phần tốn thời gian khi truy cập đĩa, xét cho cùng, thời gian dành cho chuyển động cơ học dài hơn nhiều so với thời gian dành cho chuyển động điện tử. Khi lưu trữ lượng lớn dữ liệu trên đĩa, việc định vị rõ ràng là một quá trình rất tốn thời gian, nhưng chúng ta có thể tối ưu hóa quá trình này thông qua cây B để cải thiện hiệu quả định vị khi đọc từ đĩa.

Tại sao cây B có thể được tối ưu hóa? Chúng ta có thể xây dựng một cây B nhiều cấp dựa trên các đặc điểm của cây B, sau đó lưu trữ thông tin có liên quan trên càng nhiều nút càng tốt để đảm bảo rằng số lượng lớp càng nhỏ càng tốt, để chúng ta có thể tìm thông tin nhanh hơn sau này và các hoạt động I/O của đĩa cũng ít hơn. Hơn nữa, cây B là một cây cân bằng và chiều cao từ mỗi nút đến nút lá là như nhau, điều này cũng đảm bảo rằng mỗi truy vấn đều ổn định.

Nhìn chung, cây B/B+ là cây tìm kiếm đa chiều cân bằng được thiết kế cho đĩa hoặc các thiết bị lưu trữ khác (so với nhị phân, mỗi nút bên trong của cây B có nhiều nhánh). So với cây đỏ-đen, trong cùng một tình huống nút, chiều cao của cây B/B+ nhỏ hơn nhiều so với chiều cao của cây đỏ-đen (được đề cập trong phân tích hiệu suất của cây B/B+ bên dưới). Thời gian hoạt động trên cây B/B+ thường bao gồm hai phần: thời gian truy cập đĩa và thời gian tính toán của CPU. CPU rất nhanh, do đó hiệu quả hoạt động của cây B phụ thuộc vào số lần truy cập đĩa. Khi tổng số từ khóa bằng nhau, chiều cao của cây B càng nhỏ thì thời gian dành cho I/O đĩa càng ít.

Lưu ý rằng B-tree là B-tree và - chỉ là một ký hiệu.

(2) Tính chất của cây B.

1. Xác định rằng bất kỳ nút không phải lá nào cũng có nhiều nhất M con và M>2;

2. Số lượng con của nút gốc là [2, M]; .

3. Số lượng con của các nút không phải là lá ngoài nút gốc là [M/2, M]; .

4. Mỗi nút lưu trữ ít nhất M/2-1 (làm tròn lên) và nhiều nhất là M-1 từ khóa; (ít nhất 2 từ khóa).

5. Số lượng từ khóa của các nút không phải lá = số con trỏ trỏ đến các nút con của chúng - 1;

6. Từ khóa của các nút không phải lá: K[1], K[2], …, K[M-1]; và K[i] < K[i+1]; .

7. Con trỏ tới các nút không phải lá: P[1], P[2], …, P[M]; trong đó P[1] trỏ tới cây con có từ khóa nhỏ hơn K[1], P[M] trỏ tới cây con có từ khóa lớn hơn K[M-1], và P[i] trỏ tới cây con có từ khóa thuộc về (K[i-1], K[i]);

8. Tất cả các nút lá đều nằm trong cùng một lớp; .

Đây chỉ là một cây B đơn giản. Trong thực tế, có nhiều từ khóa trong các nút cây B. Ví dụ, trong hình trên, nút 35 biểu diễn một khóa (chỉ mục) và khối đen nhỏ biểu diễn vị trí lưu trữ thực tế của nội dung được khóa này trỏ tới trong bộ nhớ, đó là một con trỏ.

5. Cây B+.

(1) Giới thiệu.

Cây B+ là một biến thể của cây B được tạo ra để đáp ứng nhu cầu của hệ thống tệp (thư mục tệp được lập chỉ mục theo từng cấp và chỉ các nút lá (tệp) cấp dưới cùng mới lưu trữ dữ liệu). Các nút không phải lá chỉ lưu trữ chỉ mục, không phải dữ liệu thực tế. Tất cả dữ liệu được lưu trữ trong các nút lá. Đây không phải là cách hệ thống tệp tìm kiếm tệp sao?

Hãy lấy một ví dụ về tìm kiếm tệp: có ba thư mục a, b và c, a chứa b, b chứa c và có một tệp yang.c. a, b và c là các chỉ mục (được lưu trữ trong các nút không phải là nút lá). a, b và c chỉ là các khóa của yang.c cần tìm và dữ liệu thực tế yang.c được lưu trữ trên các nút lá.

Tất cả các nút không phải lá đều có thể được coi là phần chỉ mục! .

(2) Tính chất của cây B+ (các tính chất được đề cập dưới đây khác với tính chất của cây B).

1. Con trỏ cây con của các nút không phải lá giống với số lượng từ khóa; .

2. Con trỏ cây con p[i] của nút không phải lá trỏ đến cây con có giá trị từ khóa thuộc về [k[i], k[i+1]]. (B-tree là một khoảng mở, có nghĩa là B-tree không cho phép trùng lặp từ khóa, trong khi B+ tree cho phép trùng lặp);

3. Thêm con trỏ liên kết tới tất cả các nút lá;

4. Tất cả các từ khóa xuất hiện trong các nút lá (chỉ mục dày đặc). (Và các từ khóa trong danh sách được liên kết đều theo thứ tự);

5. Các nút không phải lá tương đương với chỉ mục của các nút lá (chỉ mục thưa thớt), và các nút lá tương đương với lớp dữ liệu để lưu trữ dữ liệu (từ khóa);

6. Phù hợp hơn với hệ thống tập tin; .

Một nút không phải lá (như 5, 28, 65) chỉ là một khóa (chỉ mục). Dữ liệu thực tế được lưu trữ trong nút lá (5, 8, 9) là dữ liệu thực hoặc con trỏ đến dữ liệu thực.

(3) Ứng dụng.

1. Cây B và B+ chủ yếu được sử dụng để lập chỉ mục trong các hệ thống tập tin và cơ sở dữ liệu, chẳng hạn như MySQL;

6. Phân tích hiệu suất cây B/B+.

Chiều cao của cây nhị phân cân bằng có n nút là H (tức là logn), trong khi chiều cao của cây B/B+ có n nút là logt((n+1)/2)+1; .

Với tư cách là bảng tra cứu trong bộ nhớ, cây B không nhất thiết tốt hơn cây nhị phân cân bằng, đặc biệt là khi m lớn. Bởi vì thời gian CPU cho các hoạt động tìm kiếm trên cây B là O(mlogtn)=O(lgn(m/lgt)), và m/lgt>1; do đó khi m lớn, O(mlogtn) dài hơn nhiều so với thời gian hoạt động của cây nhị phân cân bằng. Do đó, khi sử dụng cây B trong bộ nhớ, phải sử dụng m nhỏ hơn. (Thông thường giá trị nhỏ nhất m=3 được lấy, trong trường hợp đó mỗi nút bên trong cây B có thể có 2 hoặc 3 nút con. Cây B bậc 3 này được gọi là cây 2-3).

7. Tại sao cây B+ lại phù hợp hơn cây B để lập chỉ mục cơ sở dữ liệu?

1. Chi phí đọc và ghi đĩa của cây B+ thấp hơn: các nút bên trong của cây B+ không có con trỏ đến thông tin cụ thể của từ khóa, vì vậy các nút bên trong của nó nhỏ hơn các nút của cây B. Nếu tất cả các từ khóa của cùng một nút bên trong được lưu trữ trong cùng một khối đĩa, khối đĩa có thể chứa nhiều từ khóa hơn và số lượng từ khóa cần tìm kiếm trong bộ nhớ cùng một lúc cũng nhiều hơn, vì vậy thời gian đọc và ghi IO tương đối được giảm.

2. Hiệu quả truy vấn của cây B+ ổn định hơn: vì điểm không phải điểm cuối không phải là nút cuối cùng trỏ đến nội dung tệp mà chỉ là chỉ mục của từ khóa trong nút lá. Do đó, bất kỳ tìm kiếm từ khóa nào cũng phải đi theo đường dẫn từ nút gốc đến nút lá. Độ dài đường dẫn của tất cả các truy vấn từ khóa đều giống nhau, mang lại hiệu quả truy vấn tương đương cho từng phần dữ liệu.

3. Vì dữ liệu của cây B+ được lưu trữ trong các nút lá và các nút nhánh là các chỉ mục, nên việc quét cơ sở dữ liệu rất thuận tiện. Bạn chỉ cần quét các nút lá một lần. Tuy nhiên, vì các nút nhánh của cây B-tree cũng lưu trữ dữ liệu, chúng ta cần thực hiện một lần duyệt theo thứ tự để quét nhằm tìm dữ liệu cụ thể. Do đó, cây B+ phù hợp hơn cho truy vấn khoảng, vì vậy cây B+ thường được sử dụng cho chỉ mục cơ sở dữ liệu.

PS: Tôi thấy có người nói thế này trên Zhihu và tôi nghĩ nó có lý:

Họ tin rằng lý do chính để sử dụng cây B+ trong chỉ mục cơ sở dữ liệu là trong khi cây B cải thiện hiệu suất IO, chúng không giải quyết được vấn đề duyệt phần tử không hiệu quả. Chính xác là để giải quyết vấn đề này mà cây B+ được tạo ra. Cây B+ chỉ cần duyệt qua các nút lá để duyệt toàn bộ cây. Hơn nữa, các truy vấn dựa trên phạm vi rất phổ biến trong cơ sở dữ liệu, nhưng B-tree không hỗ trợ các hoạt động như vậy hoặc quá kém hiệu quả.

Tóm tắt.

Trên đây là toàn bộ nội dung bài viết này, hy vọng nội dung bài viết này sẽ có giá trị tham khảo nhất định cho việc học tập hoặc công tác của bạn. Cảm ơn sự ủng hộ của bạn. Nếu bạn muốn tìm hiểu thêm về điều này, vui lòng truy cập các liên kết sau.

Liên kết gốc: https://blog.csdn.net/xlgen157387/article/details/79450295.

Cuối cùng, bài viết này về lý do tại sao MySQL database index chọn sử dụng B+ tree? kết thúc tại đây. Nếu bạn muốn biết thêm về lý do tại sao MySQL database index chọn sử dụng B+ tree? Vui lòng tìm kiếm các bài viết CFSDN hoặc tiếp tục duyệt các bài viết liên quan. Tôi hy vọng bạn sẽ ủng hộ blog của tôi trong tương lai! .