Cấu trúc dữ liệu cây B + ở Erlang

Question

Có bất kỳ triển khai nào đã biết về cấu trúc dữ liệu B+ Tree trong Erlang không?

Answer 1

Tôi chắc chắn sẽ khuyên bạn nên xem xét ứng dụng eleveldb nếu bạn thực sự cần một cây B +. Vấn đề là bạn muốn lưu trữ dữ liệu trong lá của cây, off-line trên đĩa, vì đây là nơi B + -trees thường là một tùy chọn. Ngoài ra còn có một biến thể trong Erlang thuần túy của LevelDB được gọi là hanoidb cũng khá đẹp, được viết bởi Kresten Krab Thorup. Cùng một khu vực sử dụng.

Nếu bạn cần bộ nhớ trong bộ nhớ, bạn nên xem ETS hoặc Mnesia (cái sau để phân phối). Trong Erlang những xu hướng này là giải pháp nhanh nhất vì bạn có lợi thế là không bao giờ đánh đĩa. Điều này đặc biệt đúng nếu bạn có thể thực hiện tra cứu khóa/giá trị tiêu chuẩn trên dữ liệu của mình mà không cần chạy bên trong ngữ cảnh giao dịch trong Mnesia (thực hiện đọc bẩn). Tốc độ tra cứu điển hình sau đó là 5-10 nano giây.

Answer 2

Không có thư viện độc lập mà tôi biết. Tuy nhiên, CouchDB source code rất dễ đọc và được triển khai tốt.

Answer 3

Chỉ cần một sự thay thế nếu bạn không muốn hack vào hệ thống cơ sở dữ liệu mã nguồn mở:

Chris Okasaki của Cấu trúc dữ liệu thuần túy chức năng có thể cung cấp cho bạn một số cái nhìn sâu sắc về việc thực hiện nó một mình. Bản thân cây B + không phức tạp với kinh nghiệm của tôi.

Tôi khuyên bạn nên sử dụng gb_trees nếu bạn muốn cả bộ nhớ trong bộ nhớ và thứ gì đó thấp hơn (theo một nghĩa nào đó) so với sách và chứng mất trí.