知识卡片

专业/工作

跳跃表的并发性

理解等级:未标注

跳跃表用多层有序链表给普通链表加索引,把查找、插入、删除的期望复杂度降到 O(logN)。相比红黑树,它结构更简单,更新时能把锁粒度控制得更细,因此更适合高并发有序内存表。发散:数据库内核选择数据结构时,工程可并发性常常和理论复杂度同样重要。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    原书出处

    参考来源

    《HBase原理与实践》第2章《基础数据结构与算法》