Cây tìm kiếm tĩnh: Nhanh gấp 40 lần so với tìm kiếm nhị phân
Static search trees: 40x faster than binary search (2024)
Tôi đã tối ưu hóa cây tìm kiếm tĩnh S+ để xử lý dữ liệu đã sắp xếp với thông lượng cực cao. Bằng cách tận dụng các kỹ thuật như vector hóa, prefetching và bố trí bộ nhớ thông minh, giải pháp này vượt trội hơn nhiều so với tìm kiếm nhị phân truyền thống. Mục tiêu cuối cùng là tăng tốc đáng kể việc tìm kiếm trong các cấu trúc dữ liệu lớn như mảng hậu tố trong tin sinh học.
Khi mảng dữ liệu lớn hơn bộ nhớ đệm L3, tìm kiếm nhị phân tiêu tốn khoảng 1150ns cho mỗi truy vấn, trong khi bố trí Eytzinger nhanh hơn 6 lần, chỉ mất 200ns.