赞
踩
上图是一个有序链表,我们要检索一个数据就挨个遍历。如果想要再提升查询效率,可以变种为以下结构:
现在,我们要查询11,可以跳着来查询,从而加快查询速度。
上图:
树中的每个节点,它的左子树中所有关键字值小于该节点关键字值,右子树中所有关键字值大于该节点关键字值
因为二叉搜索树是一种二叉树,每个节点只能有两个子节点,但有较多节点时,整棵树的高度会比较大,树的高度越大,搜索的性能开销也就越大
上图:
AVL树是高度平衡的(严格平衡),频繁的插入和删除,会引起频繁的rebalance,导致效率下降,它比较使用与插入/删除较少,查找较多的场景
红黑树是一种含有红黑节点并能自平衡的二叉搜索树,它满足以下性质:
和AVL树不一样,红黑树是一种弱平衡的二叉树,它的插入/删除效率更高,所以对于插入、删除较多的情况下,就用红黑树,而且查找效率也不低。例如:Java中的TreeMap就是基于红黑树实现的。
B+树是B树的升级版。B+树常用在文件系统和数据库中,B+树通过对每个节点存储数据的个数进行扩展,可以让连续的数据进行快速访问,有效减少查询时间,减少IO操作。它能够保持数据稳定有序,其插入与修改拥有较稳定的对数时间复杂度。
例如:Linux的Ext3文件系统、Oracle、MySQL、SQLServer都会使用到B+树。
稠密索引:
稀疏索引:
传统关系型数据库,一般都选择使用B+树作为索引结构,而在大数据场景下,HBase、Kudu这些存储引擎选择的是LSM树。LSM树,即日志结构合并树(Log-Structured Merge-Tree)。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。