Cây Trie vs B +

Question

Cây Trie và cây B + so sánh như thế nào để lập chỉ mục các chuỗi được sắp xếp theo thứ tự từ điển [theo thứ tự một số tỷ]? Nó cũng sẽ hỗ trợ các truy vấn phạm vi.

Từ perf. cũng như quan điểm phức tạp thực hiện.

Answer 1

Tôi muốn nói điều đó tùy thuộc vào ý bạn là gì bởi Phạm vi.

Nếu phạm vi của bạn được biểu thị là Tất cả các từ bắt đầu bằng, thì Trie là lựa chọn đúng tôi muốn nói. Mặt khác, Trie không dành cho các yêu cầu như Tất cả các từ giữa XX và ZZ.

Lưu ý rằng hệ số phân nhánh của B+ Tree ảnh hưởng đến hiệu suất của nó (số lượng nút trung gian). Nếu h là chiều cao của cây, thì n _{tối đa} ~~ b ^h. Do đó, h ~~ log (n _max)/log (b).

Với n = 1 000 000 000 và b = 100, chúng tôi có h ~~ 5. Do đó nó có nghĩa là chỉ có 5 con trỏ dereferencing cho đi từ gốc đến lá. Nó thân thiện với bộ nhớ cache hơn so với Trie.

Cuối cùng, B+ Tree được thừa nhận là khó thực hiện hơn so với Trie: nó cao hơn mức độ phức tạp Red-Black Tree.

Answer 2

Wikipedia có một số sự kiện phức tạp về thuật toán: B+ tree (phần Đặc điểm), Trie (không may lan rộng khắp bài viết). Hy vọng rằng sẽ giúp.

Answer 3

Phụ thuộc vào công việc thực tế của bạn:

• Nếu bạn muốn nhận được toàn bộ cây con, một B + Tree là sự lựa chọn tốt nhất của bạn bởi vì nó là không gian hiệu quả.
• Nhưng nếu bạn muốn để có được những N trẻ em đầu tiên từ một substree, sau đó một Trie là sự lựa chọn tốt nhất bởi vì bạn chỉ cần truy cập các nút ít hơn trong một kịch bản B + Tree.
• Nhiệm vụ phổ biến nhất được xử lý tốt bởi Trie là hoàn thành tiền tố từ.