索引设计的几个常用算法

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(log₂N)与树的深度相关，那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘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，如需转载请自行联系原作者