本文主要是介绍什么DS适合做数据库的索引，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
一、线性表？
二、搜索二叉树？
三、哈希表？
四、B树？
五、B+树？（答案是这个）
数据库索引具有很强大的功能，他可以在海量的数据中查找特定的值，或者某一个范围的数据集合，而且非常稳定。
那么什么数据结构支持它能高效的查询呢？
一、线性表？
首先最简单的各种线性表就不可能了，时间复杂度是O(N)。
二、搜索二叉树？
实际上二叉搜索树的时间复杂度也是O(N)，如果数据是升序或者降序，将会是一个倾斜二叉树，显然不能提供良好的稳定性。
如果遇到差的情况，需要多次硬盘IO。
但是总所周知，数据库很娇贵，硬盘IO速度很低，我们要经可能减少硬盘的IO
三、哈希表？
哈希表的确很快，搜索效率达到了常数级，而且稳定；
但是也不行。
我们都知道，哈希表的底层是用要查询的数据使用对应哈希函数，散列到哈希表对应位置的，这就是为什么哈希表的查询是O（1）的原因，但是这也有一个致命的弊端。
》》》就是它不能查询某一个范围的数据集合。
因为通过哈希函数得到的下标，与临近的数据之间并没有实质上的联系。
四、B树？
B树就是平衡的二叉搜索树，但是他的每一个节点不在是单个数据，而是一组排好序的数据集合：
这样树的高度得到减少，而且每次IO可以获得多组数据，搜索效率得到了极大提升。
但是，它也不适合作为索引的数据结构。
原因很简单，它不够稳定，有时候如果查询到树顶端的数据，就会很快，有时候要查询的是叶子结点的数据相对来讲就会慢很多。
稳定性是难能可贵的有点，这样程序的运行效率才是可以预测的，才是可靠的。
五、B+树？（答案是这个）
B+树是B树的改良版本。
B+树中，只在叶子节点存储实际的数据，其他节点只存储主键（也就是一个数字）
这样，虽然牺牲了一少部分性能，但是可以使数据结构变得稳定，每一次数据查询，都需要走到叶子结点。
想要实现范围查询也很简单，把叶子节点通过指针串联成一个链表形式的数据结构即可。
这样就得到了一个查询快速，性能稳定，可以范围查询，还节约了部分空间的数据结构了。
这篇关于什么DS适合做数据库的索引的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
