Generally patch looks close to committable shape for me. I'm going to revise code and documentation again, split it up, and then propose to commit.
I've revised this patch again. This revision includes a lot of code beautification, adjustments to comments and documentation. Also, after reviewing bug fix [1] I found that we don't need separate memory context for queue. traversalCxt looks perfectly fine for that purpose, because there it's single scan lifetime. Also, it appears to me that it's OK to be a single patch: besides KNN SP-GiST and opclasses it contains only extraction of few common function between GiST and SP-GiST.