Xin lỗi, đây không phải là câu trả lời SQL, mà là một cách để đạt được hiệu suất có thể dự đoán trước giả sử các ràng buộc nhất định đối với dữ liệu của bạn.
Dữ liệu thay đổi thường xuyên như thế nào? Nếu có thể, bạn có thể tính toán trước một biểu đồ của mọi thực thể 5 láng giềng gần nhất và sử dụng biểu đồ đó để tăng tốc lựa chọn của bạn.?
Nếu dữ liệu này chủ yếu chỉ được đọc, thì ...
Làm thế nào đồng đều các điểm được phân bố? Nếu khá đồng đều và biết rõ về phân phối, thì bạn có thể lập bản đồ khoảng cách của riêng mình bằng cách tính mọi tọa độ và chỉ mục trong một bảng băm.
Nếu bạn không cần có dữ liệu trong cơ sở dữ liệu, hãy chuyển dữ liệu đó ra tệp ánh xạ bộ nhớ để tra cứu băm nhanh. (70 triệu bản ghi sẽ dễ dàng vừa với bộ nhớ).
Tôi đã sử dụng kiến trúc này để tạo các tìm kiếm dưới mili giây cho quảng cáo hiển thị hình ảnh và mức độ liên quan của công cụ tìm kiếm.
==Công phu ==
Bạn chỉ cần tạo một lưới các ô vuông có kích thước cố định (như bàn cờ), và bạn ánh xạ từng điểm vào lưới và bạn tạo một danh sách các đối tượng phù thủy thuộc về mỗi ô lưới - nếu bạn điều chỉnh kích thước của từng ô một cách chính xác, trung bình bạn phải có 5-50 điểm trong mỗi ô vuông - Về nguyên tắc, đây là một cây bốn cây nhưng không có cây vì đơn giản.
Đối với mỗi nhóm trống sau khi bạn đã phân tán tất cả dữ liệu trong các nhóm, bạn thêm thông tin về các nhóm gần nhất có chứa dữ liệu.
Giờ đây, bạn có thể đánh số từng nhóm từ trái sang phải-dòng-ny-dòng để mỗi nhóm có một số duy nhất có thể được tính toán từ các tọa độ - và bạn chèn từng nhóm vào bảng băm hoặc nếu không gian cho phép một bảng tra cứu đơn giản.
Bây giờ khi bạn có truy vấn của mình, bạn chỉ cần tính toán nhóm sẽ ánh xạ tới và bạn sẽ nhận được danh sách các đối tượng trong nhóm đó hoặc bạn sẽ nhận được một nhóm 'trống' chứa các con trỏ đến nhóm gần nhất có nội dung .
Điều đó sẽ cung cấp cho bạn danh sách ứng cử viên đầu tiên của các đối tượng mà bạn đang tìm kiếm, và bây giờ bạn chỉ cần chạy và xem whcih một là đối tượng gần nhất.
Trong 99% trường hợp sẽ là như vậy - nhưng nếu bạn lo lắng về (a) hoặc là một số chất ngưng tụ trong các nhóm tiếp theo thực sự gần hơn, thì chỉ cần kiểm tra 8 nhóm xung quanh và xem liệu bạn có thể tìm bất kỳ gần đó hơn.
Nếu bây giờ bạn cũng muốn nhận danh sách tất cả các đối tượng gần nhất, thì cũng tính toán một mạng đơn giản gồm 5 neigbours gần nhất cho mỗi obejct, vì vậy bạn sẽ có cấu trúc dữ liệu như A -> {B, C, D , E, F}, B -> {A, D, G, H, I}, C -> {A, J, K, G, M} ....
Điều đó sẽ tạo thành một mạng đơn giản mà giờ đây bạn có thể đi qua với một biến thể của Dijkstra tại đây để nhận được tất cả các điểm liền kề với điểm gần bạn nhất.
Việc xây dựng cấu trúc dữ liệu sẽ mất thời gian, nhưng sau khi hoàn thành và việc tra cứu đúng và trả về tập dữ liệu có thể được thực hiện trong sub mili giây (không bao gồm bất kỳ thông tin liên lạc http hoặc off-box nào củacause)
Hy vọng điều này sẽ hữu ích.
