MySQL为何选择B+树存储索引

声明
本文所述的各种数据结构(二叉树等)，均不考虑重复值的情况，本文简述各种数据结构的区别仅仅只是为了理解MySQL索引的需要而做的铺垫。

什么是索引

提起索引，大家都知道，建立索引可以让数据库查询更快，那么索引究竟是什么？我想这就不是每个人都能说得出来了。
索引，是数据库管理系统中一个排序的数据结构，并用以协助快速查询、 更新数据库表中数据。
是的，索引是一种数据结构，但是那么多的数据结构中为何MySQL要选择B+树呢？接下来就让我们一起来了解下B+树相对于其他数据结构有何独特之处！

二分查找法(Binary Search)

首先让我们自己想一想，如果让我们去设计，我们会怎么去存储？我想大部分人想到就是用链表或者数组去存储数据，然后再按默认的顺序排好，再去查找，而一个排好顺序的链表我们就可以通过二分查找法来高效查询。

二分查找也称折半查找，是一种效率较高的查找方法。比如有1-10十个数，我们要找到8，先从中间开始找5，然后发现8比5大，可以把5左边的数去掉，剩下6-10，再从中间开始找，依次类推，直到找到8为止。但是这种查找法有一个前提是数据必须是有序的，而且这种属于链表式的存储，我们一但要插入或者修改一个数据，可能会伴随着大量的下标移动，比如我们把1-10放在数组里面，下标分别对应0-9，然后现在要插入一个0，为了保证有序，0必须排在第一位，那么1-10所有的数据下标都要往后移动一位，这种就有点大动干戈了，所以为了解决这个问题，我们就有了二叉树。

二叉查找树(BST）

二叉查找树简称二叉树(BST)，英文全称：Binary Search Tree，这是一种什么样的数据结构呢？请看下图

在上面这棵树中，我们要找到8，先从根节点6开始比较，发现8比6大，就往右边走，就可以找到8

阅读全文»