| ▲ | hinkley 2 hours ago | |||||||
I have to say I was always on the fence about Bill Pugh (Mr Skiplist). Some of his concurrency ideas were pretty good but Skip Lists were about the same time I was realizing that theoretical and practical design for performance had diverged and skip lists were a huge cache miss liability. It didn't hurt that a few people I was aware had tried them had gone back to something else due to live performance analysis being negative or inconclusive (If you can't prove one thing is better than the other, you use the simpler one, and skiplists are not simple) | ||||||||
| ▲ | infamouscow an hour ago | parent [-] | |||||||
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. | ||||||||
| ||||||||