Om du inte har något emot att offra komplexiteten i infogning/uppdatera/ta bort operationerna för snabbhet på markeringen, kan du alltid lägga till ett sekvensnummer och se till att det bibehålls vid infoga/uppdatera/ta bort, och när du gör ett val väljer du helt enkelt på ett eller flera slumptal inom detta intervall. Om kolumnen "sekvens" är indexerad tror jag att det är ungefär så snabbt som du kommer att få.
Ett alternativ är att "blanda". Lägg till en sekvenskolumn, infoga slumpmässiga värden i den här kolumnen, och när du väljer poster, ordna efter sekvenskolumnen och uppdatera de valda postsekvenserna till nya slumpmässiga värden. Uppdateringen bör bara påverka de poster du har hämtat, så det bör inte vara för dyrt ... men det kan vara värt att köra några tester mot din datauppsättning.
Detta kan vara en ganska ond sak att säga, men jag säger det ändå ... finns det någonsin ett behov av att visa "slumpmässiga" data? om du försöker visa slumpmässiga poster kan du göra något fel.
Tänk på Amazon ... visar de slumpmässiga produkter, eller visar de populära sådana, och "saker som andra människor köpte när de tittade på det här". Ger SO dig en lista med slumpmässiga frågor till höger här, eller en lista med relaterade? Bara lite att tänka på.