为什么数据库索引多用B+树

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

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

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

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

（编辑：漯河站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!