程序员经典面试题，为什么数据库索引多用B+树

程序员经典面试题，为什么数据库索引多用B+树

最近很多小伙伴都参与了面试更换了工作，校招也已经开始了。最近面试了几个实习生，感觉基础能力都不大行，数据库在程序员的面试中占有举足轻重的一个作用。今天我们来讲一讲数据库的索引是什么?

索引，就跟我们的书本的目录一样，如果一本书没有目录，那么你要找某一个知识点，那自然是相当费劲的。数据库的索引就是扮演这样的角色，索引会告诉你对应的数据存放的磁盘地址，就好比目录上面的页数。那么数据库的“目录”究竟长什么样子呢?

常见的数据库索引有下面三种类型，第一是哈希表，哈希表相信大家都已经不陌生了，我们可以将数据库的索引字段后哈希并保存下来。只要哈希算法设计得合理，我们可以非常快地找到对应数据的一个存放地址，然后到对应的存放地址就可以快速地找到数据。那么，哈希索引有什么缺点呢?首先是哈希表比较适合在内存中使用，但是如果要落盘，就比较麻烦了，特别是哈希表扩容的时候，磁盘的很多数据都会修改。第二，哈希表没办法进行一个区间的筛选。

第二种则是数组索引，与上述的哈希表类似，但又有所不同。与哈希索引类似，数组索引的效率也是非常高的，在一个有序数组里面去查找元素，我们只要进行二分查找即可。但是数组索引的问题也是非常地明显，那便是插入非常的麻烦，你插入一个新的元素，就要把后面所有的元素都往后移动一下。所以，数组索引我们一般只有静态数据才会使用。

有序数组都讲了，那么接下来肯定就是二叉树了，我们说的二叉树当然是二叉排序树，二叉排序树相对与数组，比较大的优点是方便插入。但是同时也存在这么一个问题，因为索引的数据可能存在磁盘，那么如果索引的数据超过1000条的时候，就有可能要经过10次才能够找到最终的数据，而磁盘IO的瓶颈在于寻道跟旋转，效率必然会降低。所以，我们要尽量地减少在磁盘中寻道跟旋转的次数，所以多叉树就被广泛应用在数据库索引当中了。而在多叉树中，比较常被使用的，便是B+树。

现在你知道了为什么数据索引有哪些，以及为什么B+树被广泛应用的道理了吧。欢迎大家关注我，共同学习，共同进步。大家的支持是我继续唠嗑的动力。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。