索引设计的几个常用算法-阿里云开发者社区

开发者社区> 范大脚脚> 正文

索引设计的几个常用算法

简介:
+关注继续查看

B+、B- Tree(mysql,oracle,mongodb)

主要用在关系数据库的索引中,如oracle,mysql innodb;mongodb中的索引也是B-树实现的;还有HBase中HFile中的DataBlock的索引等等。

动态查找树主要有:二叉查找树(Binary Search Tree),平衡二叉查找树(Balanced Binary Search Tree),红黑树(Red-Black Tree ),B-tree/B+-tree/ B*-tree (B~Tree)。前三者是典型的二叉查找树结构,其查找的时间复杂度O(log2N)与树的深度相关,那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题:就是大规模数据存储中,实现索引查询这样一个实际背景下,树节点存储的元素数量是有限的(如果元素数量非常多的话,查找就退化成节点内部的线性查找了),这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁,进而导致查询效率低下,那么如何减少树的深度(当然是不能减少查询的数据量),一个基本的想法就是:采用多叉树结构(由于树节点元素数量是有限的,自然该节点的子树数量也就是有限的)。

也就是说,因为磁盘的操作费时费资源,如果过于频繁的多次查找势必效率低下。那么如何提高效率,即如何避免磁盘过于频繁的多次查找呢?根据磁盘查找存取的次数往往由树的高度所决定,所以,只要我们通过某种较好的树结构减少树的结构尽量减少树的高度,那么是不是便能有效减少磁盘查找存取的次数呢?那这种有效的树结构是一种怎样的树呢?

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发,自然就想到平衡多路查找树结构,也就是B-tree,即B树结构,B树的各种操作能使B树保持较低的高度,从而达到有效避免磁盘过于频繁的查找存取操作,从而有效提高查找效率。

Hash表+桶(redis)

mysql中的adaptive hash index,redis中的数据存储实现都是采用hash,可以高效的进行数据的查询。

 哈希表(Hash table,也叫散列表),是根据关键码值(Key value)而直接进行访问的数据结构。也就是说,它通过把关键码值映射到表中一个位置来访问记录,以加快查找的速度。这个映射函数叫做散列函数,存放记录的数组叫做散列表。

哈希表的做法其实很简单,就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字,然后就将该数字对数组长度进行取余,取余结果就当作数组的下标,将value存储在以该数字为下标的数组空间里。
而当使用哈希表进行查询的时候,就是再次使用哈希函数将key转换为对应的数组下标,并定位到该空间获取value,如此一来,就可以充分利用到数组的定位性能进行数据定位

数组的特点是:寻址容易,插入和删除困难;而链表的特点是:寻址困难,插入和删除容易。综合两者特性,设计一种寻址容易,插入删除也容易的数据结构,如拉链法实现的哈希表。

Booleam Filter(HBase)

HBase中的rowkey设置建立Booleam Filter映射,用于快速判断rowkey是否在一个HFile中。在分布式数据库中用的比较多。

基于BitMap的存储结构,采用的是哈希函数的方法,将一个元素映射到一个 m 长度的阵列上的一个点,当这个点是 1 时,那么这个元素在集合内,反之则不在集合内。

这个方法的缺点就是当检测的元素量很多时候可能有冲突,解决方法就是使用 k 个哈希 函数对应 k 个点,如果所有点都是 1 的话,那么元素在集合内,如果有 0 的话,元素则不再集合内。

 


本文转自邴越博客园博客,原文链接:http://www.cnblogs.com/binyue/p/3723899.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
[软考考点解析]软件设计师--计算机常用端口号
1. 题目 若1台服务器只开放了25和110端口,则该服务器可提供____服务。 A email B WEB C DNS D FTP
10 0
如何设计高效合理的MySQl查询语句?23种常用类型汇总(珍藏版)
MySQL对于很多Linux从业者而言,是一个非常棘手的问题,多数情况都是因为对数据库出现问题的情况和处理思路不清晰。在进行MySQL的优化之前必须要了解的就是MySQL的查询过程,很多的查询优化工作实际上就是遵循一些原则让MySQL的优化器能够按照预想的合理方式运行而已。
1139 0
Swagger异常定位纪实,是用的不对,还是Swagger本身设计问题
swagger ui是一个采用注解驱动的接口文档工具,目前已支持标准的open api v3规范协议,所以不仅可以在java项目里使用,每个语言都有相应的open api实现。项目集成swagger后,可以生成导出open api v3格式化的元数据集,有了这个接口元数据,你可以在任何支持v3协议的ui上展示你的api信息。在前后端分离的项目中,swagger ui的出现,大大提高了前后端联调的效率。swagger ui在解析注解标注的元数据信息时,特别场景下会抛异常,而且抛的异常没有直观的有价值的异常信息,所以深入的debug了一番,虽然最后问题解决很简单,但是过程非常曲折。故将bug定位过
604 0
[转贴]40种网站设计常用技巧(Javascript)
回到家了,没有开发环境,这几天只能看网页学习一下。这是csdn上转载的一篇,有些东东还是值得一看的。1. oncontextmenu="window.event.returnValue=false" 将彻底屏蔽鼠标右键no 可用于Table 2.
659 0
我在架构设计和代码开发中的一些常用原则
在日常的开发和设计过程中,大家对技术设计上的一些问题往往会面临很多的选择,不同的人会有不同的选择。本文介绍的就是我在工作中遇到的一些问题而总结和使用到的一些常用原则。
1175 0
常用的消息摘要算法小总结
今天偶然的学习了一下几种关于消息摘要算法的知识。个人觉得很好。应着老话“好记性不如烂笔头”,我就码了几行代码咯。 算法嘛,没什么好说的了。毕竟是设计者智慧与汗水的结晶,也是时代进步的推动力。
1009 0
常用开源框架中设计模式使用分析
说起来设计模式,大家应该都耳熟能详,设计模式代表了软件设计的最佳实践,是经过不断总结提炼出来的代码设计经验的分类总结,这些模式或者可以简化代码,或者可以是代码逻辑开起来清晰,或者对功能扩展很方便...。
8653 0
+关注
3656
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载