Remix.run Logo
▲ infamouscow an hour ago

B+tree were designed around optimized IO in the era of magnetic storage, they're inherently cache-friendly. Skiplists are the same thing as a b+tree but the structure is inverted, which makes skiplists more to concurrent writer-friendly than b+trees. Different tradeoffs.

▲hinkley an hour ago | parent [-]

But more cache misses, due to the variable pointer length structure.

That cost varies from chip generation to generation, but it does seem to be the case that b trees win in more generations than they lose.