为了让链表也能支持二分查找,我们可以在链表的基础上加上一层目录,即一层索引链表:
当我们访问某个节点时,先访问索引链表,通过索引链表进行二分过滤,在索引链表找到结点后,顺着索引链表的结点向下,找到原始链表的结点...----
跳表和B+ tree相同之处
相同:
B+树和跳表都是在最底层包含所有用户数据,并且都是按顺序排列,时候范围查询
B+树和跳表利用索引层实现二叉查看,从而提高性能
不同之处也就是二者使用场景的区别了...----
跳表和B+ tree在数据插入方面的性能
B+ tree插入性能分析
B+ Tree本质是一种多路平衡树,关键在于"平衡"二字,它的含义是子树们的高度层级尽量一致(最多差一个层级),这样在搜索的时候...当我们向数据库表不断插入记录时,为了维持B+树的平衡,B+树会不断分裂调整数据页。...----
跳表插入性能分析
当我们需要往跳表中插入数据时,是通过随机函数产生当前节点的层数,然后更新每一层索引,往其中加入一个节点,如果当前层数不足,就新添加一个索引层。