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 Cấu trúc cây: MongoDb sử dụng cây B-tree hay cây B+? Được tác giả sưu tầm và sắp xếp, nếu bạn quan tâm đến bài viết này thì hãy thích nhé.

  .

Liên quan đến B-tree và B+ tree, có một câu hỏi kinh điển trên Internet: Tại sao MongoDb sử dụng B-tree, trong khi MySQL index sử dụng B+ tree?

Nhưng liệu MongoDb có thực sự sử dụng B-tree không?

Sau khi tham khảo thông tin, tôi tìm thấy câu trả lời từ trang web chính thức của MongoDb và trang web chính thức của WiredTiger. Mô tả về công cụ lưu trữ trên trang web chính thức của MongoDb như sau: Bắt đầu từ MongoDb 3.2, nó sử dụng WiredTiger làm công cụ lưu trữ mặc định.

Địa chỉ tài liệu: WiredTiger Storage Engine — MongoDB Manual.

Từ tài liệu trang web chính thức của WiredTiger, chúng ta có thể biết rằng WiredTiger sử dụng cây B+ làm cấu trúc lưu trữ.

Địa chỉ tài liệu: WiredTiger: Điều chỉnh kích thước trang và nén.

Tại sao nhiều tài liệu lại nói rằng MongoDb sử dụng B-tree làm cấu trúc dữ liệu lưu trữ? Tôi nghĩ có thể có hai lý do: một lý do có thể là bản thân B+ Tree là một tối ưu hóa của B-tree, vì vậy nhiều người gọi trực tiếp B+ tree là B-tree. Một lý do khác có thể là trước MongoDb 3.2, B-tree đã được sử dụng làm cấu trúc dữ liệu lưu trữ.

Tôi chưa khám phá sâu về hai lý do này. Bạn bè nào có câu trả lời có thể để lại tin nhắn để thảo luận. Nhưng tôi biết rằng dù lý do là gì thì cũng sẽ không ảnh hưởng đến cuộc thảo luận của chúng ta về vấn đề này. Trên bề mặt, chúng ta đang thảo luận về các cấu trúc dữ liệu được lưu trữ trong MongoDb và MySQL, nhưng thực tế chúng ta đang thảo luận về đặc điểm của hai cấu trúc dữ liệu, B-tree và B+-tree.

Do đó, liệu MongoDb có sử dụng cây B-tree hay cây B+ không. Chỉ cần chúng ta hiểu được sự khác biệt giữa cây B-tree và cây B+, chúng ta có thể chọn đúng cấu trúc dữ liệu vào đúng thời điểm.

Tính năng lớn nhất của B-tree và B+ tree là B-tree có độ phức tạp thời gian thấp hơn khi truy vấn các bản ghi cụ thể. Cây B+ thuận tiện hơn cho các truy vấn phạm vi và cây B+ phẳng hơn cây B.

MongoDb là cơ sở dữ liệu phi quan hệ và hiếm khi thực hiện truy vấn phạm vi trên các bảng đã tham gia. Nếu đây thực sự là một tình huống sử dụng rất điển hình cho MongoDb, thì việc sử dụng B-tree thực sự có thể tăng tốc các truy vấn.

Nhưng trên thực tế, sau MongoDb 3.2, nó sử dụng cây B+ làm cấu trúc dữ liệu. Cây B+ có nhiều ưu điểm hơn trong truy vấn phạm vi, có thể là do cây B+ phẳng hơn, cho phép tìm dữ liệu nhanh hơn và tăng tốc độ tìm kiếm. Cũng có khả năng tính năng truy vấn phạm vi của MongoDb được sử dụng rộng rãi hơn.

Đến thời điểm này, bạn có thể hơi bối rối. Tình hình thực tế thế nào?

Thực ra, tôi vẫn chưa tìm ra câu trả lời. Đây là nơi suy nghĩ của tôi kết thúc và tôi vẫn chưa tìm ra câu trả lời nào tốt hơn. Thay vì để thai nhi chết trong bụng mẹ, tôi có thể viết ra và thảo luận với mọi người. Có lẽ sớm thôi tôi sẽ nhận ra sự thật đằng sau nó, và khi đó tôi sẽ chia sẻ nó với bạn.

Sau khi viết xong, một câu hỏi khác nảy ra trong đầu tôi: Tại sao MongoDb lại sử dụng cây B+ thay vì cây nhị phân cân bằng? Câu trả lời thực ra rất đơn giản - đó là vì cây B cần có khả năng tải lượng dữ liệu lớn, nếu không thì nó không thể thực hiện được truy vấn và sắp xếp lượng dữ liệu lớn như vậy.

Địa chỉ gốc: https://mp.weixin.qq.com/s/UPhSel0xZuhJp3efiL10ig.

Cuối cùng, bài viết này về cấu trúc cây: MongoDb sử dụng cây B-tree hay cây B+? Đây là phần cuối của bài viết. Nếu bạn muốn biết thêm về cấu trúc cây, MongoDb sử dụng B-tree hay B+ tree? Vui lòng tìm kiếm các bài viết trên 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! .