数据库索引有关的数据结构你搞清楚了吗？

数据库索引可是Java后端开发经常打交道的东西，小豪在一次面试中就被这个问题给难住了，我们一起来看看小豪是怎么出糗的嘻嘻，大家一起笑话他。

文章人物及背景：
小豪： 23岁，武汉某双非本科不知名专业大学四年级学生，成绩一般，面临毕业，对后端开发、Java很感兴趣，正求职找工作。
宇哥: 跟小豪通过租房认识，两人是室友，26岁，毕业后长期从事软件开发工作，是一个半吊子工程师，兴趣爱好是吹牛，不打草稿那种。

1.1 面试失败

小豪热爱编程，觉得写代码、做网站开发无敌酷炫雕炸天，在某站上看完了某马基础班和就业班的教学视频，觉得自己已经成为了斗宗强者，踌躇满志，海投简历，终于被某单位临幸，欣喜若狂，欣然赴约。

这次的面试官是一个中年大叔，发量尚可，不过发际线有力争上游的趋势，穿着浅蓝色的衬衫，最上面的一颗扣子没有扣上，衣领随意翻着，不苟言笑。识人面相的小豪暗道一声不妙，这个面试官可能不简单。

面试官：先自我介绍一下，重点说一下你做过的项目。

小豪心里一乐，嘿嘿，昨晚刚刚背过的，一阵摇头晃脑过后…

面试官： 你刚刚提到了数据库优化，那你有哪些优化经验？

小豪：（依然自信）创建索引、分表分库（开玩笑，我在某论坛上可是背过好几种优化方法的）

面试官微微一笑：创建索引？那你简单说说你给项目里的表创建索引的时候有哪些经验，会思考什么？

小豪面色一僵： 呃，这个，我想想…

漫长的十秒钟过后，小豪的额头已经出现了汗水，创建索引的那些劳什子原则我倒是背过，可现在想不起来了，本来就没看懂过，这可如何是好？

面试官嘴角一撇，笑着说：没关系，你先回忆下什么是索引？

小豪：哦，索引，嗯，就是类似于字典前面的那些拼音首字母，偏旁部首？

面试官微笑：出去帮我关一下门。

小豪拿着背包落荒而逃…

1.2 啥都懂一点儿的宇哥

下班回到家的宇哥看见小豪坐在笔记本电脑前面不停刷着某博客，记着笔记，嘴里还絮絮叨叨的说着什么。

宇哥：哟，这么爱学习咧，看啥呢？

小豪：数据库索引呗，今天面试官问我什么是数据库的索引，我都不知道准确定义，更别提那些什么创建索引的经验和索引优化方法了，不是我说，这些文章都列的条条框框的，明明是写的中文，我就是看不懂，鬼才记得住呀，这面试官，真讨人嫌，问我这个。

宇哥：哈哈哈，你在这抱怨也没用，数据库索引可是门大学问，你要做后端开发，肯定要懂这个东西。你得牢牢记住索引是一种数据结构，是排好序的、利于快速查找的一种数据结构。

小豪：啊，我记起来了，索引是那啥B减树还是B+树来着。

宇哥：你啊，可别闹笑话了，B-树就念作B树，千万别念成B减树，况且数据库中创建表时选择的引擎不同，索引采用的数据结构也会不同。不过网上一般都说的是InnoDB引擎，它使用了B+树索引模型，所以索引存储在B+树中，但是索引的常用数据结构可不止这些。

小豪：啊啊啊啊，宇哥你教教我把，我太难了，跟我把索引的常用数据结构讲一讲，我得知道它们的优缺点，下次面试才能游刃有余不是。

宇哥：行吧，哥哥今天心情好，刚好知道那么一点点，就跟你好好把索引的数据结构说道说道，让你下次也能跟别人吹吹水。

1.3数据库索引的常用数据结构对比

1.3.1哈希表和有序数组

宇哥：索引的出现是为了提高查询效率，它的实现方式有很多种。

第一种是哈希表，你也知道，哈希表里面存储的是key-value键值对。如果利用哈希表来存储索引的话，得先利用哈希函数把key换算成数组中对应的一个Index位置，然后把value放在这个位置，如果多个key换算后得到了相同的index，那么就在这里追加一条链表，存储哈希值相同的key-value对象。我给你画张图你就一目了然了，比如你现在有一个用户表，存储了用户id和用户name，用哈希表结构进行存储。

对着上面的哈希表索引，你可以发现，如果给你一个指定的id值让你查询数据，先根据哈希函数换算数组的index值，如果该位置有多个值，那么遍历链表即可，查询速度还是很快的，但你发现有什么缺点没？

小豪：很明显，接着你的思路，给定的id值查询速度是还可以，但是如果给定的是一个id范围查询条件，比如我要查询的是[id_noX，id_noY]之间的数据的话，因为哈希表是无序的，所以必须对这个索引表遍历一遍，那就太慢了。

宇哥：对的，说到点子上了。所以，哈希表这种结构适用于只有等值查询的场景，比如Memcached及其他一些NoSQL引擎。

小豪：就这一个用户表来说，如果id_no是递增而且唯一的，可以选择使用有序数组来存储呀，等值查询时有序数组直接按index查询，范围查询时可以用二分法查找， 查询速度应该可以满足的呀，快夸我快夸我！

宇哥：按你说的，查询速度是满足了，但是你有没有想过如果有插入或者更新数据等操作的时候，有序数组需要的操作量有多大？

小豪：如果更新数据的话就得挪动复制后面所有的元素，的确得不偿失，成本太高了。

宇哥：有序数组索引只适用于静态存储引擎，比如你要保存的是某一类不会再修改的数据。

1.3.2 二叉树和多叉树

宇哥：实际上数据库一般都选择使用树结构来存储索引，因为树结构在保证有序的同时还能保证时间复杂度为O（logN），查询速率也比较快。

小豪：宇哥，我觉得二叉树的查询速率已经够快了，从算法逻辑上看二叉树和B树、B+树这些多叉树也没什么差别，为什么一般选择使用多叉树而不是二叉树来做为存储索引的数据结构呀。

宇哥：好问题，实际上这和索引的存储位置有关系，当数据量比较大的时候，索引是需要非常大的存储空间的，因此将索引保存在内存里显然不太现实，所以索引都是保存在磁盘空间里面，使用的时候再从磁盘读取到内存，这就是磁盘IO。

当使用索引查询数据时，计算机需要从一页一页的磁盘页中将索引读取到内存中，每页磁盘页对应着树结构的一个节点。我问你，假设你要查询的那个数据在存储树结构的叶子节点里，你觉得是树 “高瘦” 一点好，还是树 “矮胖” 一点好呢？
小豪：肯定是矮胖一点好呀，你说了，每查询一个树节点相当于经过一次磁盘IO，读取了一页磁盘页，磁盘IO每次花费时间差不多8-10ms的样子，这个时间开销是特别巨大的，所以树越矮，查询过程中需要经过的树节点越少，需要时间也就越少，所以说数据库索引一般选择多叉树，而不是二叉树，我觉得我可以画个图展示这个过程。

宇哥：不错哦，通过图片我们可以发现B树的高度足够低，IO次数少，对查询的性能提升更强。多叉树中某一节点内部的元素可能会多一些，但是同一节点中的数据比较都是在内存中完成的，耗时几乎可以忽略，这就是多叉树的有优势。

1.3.3 B+树

宇哥：B+树是B树的变体，具有着比B树更高的查询性能。在详细地介绍B+树之前，我们先从条件定义上对比一下两种多叉树，看不懂也没关系，后面对照着图和过程就能理解了。这里跟你讲定义，我只是想装个B。

小豪：…原来你心里有棵B树。

一个m阶的B树具有如下特征

1.根节点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子,其中m/2 <= k <= m。
3.每一个叶子节点都包含k-1个元素，其中m/2 <= k <= m。
4.所有叶子节点都位于同一层。
5.每个叶子节点中的元素从小到大排列，节点当中k-1个元素正好是k个孩子包含的元素的值域划分。

一个m阶的B+树具有如下特征

1.有k个子树的中间节点包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.所有的中间节点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

小豪：宇哥，这些定义我听懂了，真的（真诚脸）。
宇哥：你快拉倒吧，凑弟弟，看不懂也没关系，定义其实不重要，你只要搞清楚两者之间的差别特别是B+树的优点，面试就可以吹牛了，我给你画张图，你就一目了然啦。

宇哥：你看上面这棵美丽的B+树，节点之间有重复元素，叶子节点之间还用指针连在一起。每一个父节点的元素都会出现在子节点中，成为子节点的最大或者最小元素。

• B+树和B树最大的不同是在B树中无论中间节点还是叶子节点都存储了索引元素指向数据库种某一行的数据记录（该信息可能是指向数据库数据记录的指针，也可能就是需要查询的数据记录，这由具体索引类别决定），而在B+树种只有叶子节点存储该信息，其余中间节点仅仅是索引，没有和任何数据关联。因此，由于B+树的中间节点没有存储数据记录，所以同样大小的磁盘页可以容纳更多的节点元素，也就是说在数据量相同的情况下B+树的结构比B树要更加矮胖哦。
• B树做范围查询时，比如先自顶向下找到左边界元素，需要依靠只能依靠繁琐的中序遍历去寻找右边界元素：叶子节点–中间节点–根节点–中间节点–叶子节点…
  而B+树由于再叶子节点之间由指针连接，只需要遍历叶子节点链表就可以迅速完成范围查找。

总结一下B+树的优势：

1. 单一节点存储更多的元素，使得查询的IO次数更少。
2. 所有查询都要查找到叶子节点，查询性能稳定。
3. 所有叶子节点形成有序链表，便于范围查询。

1.4充满信心的小豪

小豪：宇哥有点东西啊，那B+树岂不是无敌了？

宇哥：技术一直都在发展进步哦，没有最好的技术，只有更符合业务需求的技术，现在跳表、LSM树等数据结构也被用于引擎设计中，你要是感兴趣可以接着研究呀。

小豪：哎，光B树和B+树我都还得反复学习咧，下次面试我应该可以得到来自面试官的肯定，哈哈哈。

宇哥：有信心是好事，不过这这点内容只能算是皮毛啦，数据库索引可是门大学问。

小豪：知道啦知道啦，我算是明白了，实际上数据库索引其他的一些什么优化、原则啥的，都跟底层的数据结构脱不开关系。

宇哥：哈哈，这也是我今天跟你讨论这个的原因，溜了溜了，吃饭去。

小豪：走走，我请客，方便面加火腿！

宇哥：可以的，冲！

画外音

兄弟萌，妹妹萌，用心写故事，用心学技术，写的不好多包涵保函。
LearnJava，冲呀，想看就私信评论留言催更撩我啊，凑弟弟，凑妹妹们！

参考文献

[1]程杰. 大话数据结构 [M].清华大学出版社，2011年.

更多

对我的文章感兴趣，欢迎查看我的其他系列博客：
《Java牛客网剑指offer编程题》
《跟凑弟弟一起修炼集合框架》
《Java多线程大闯关》
《Java IO流大闯关》
《数据库和Redis》
持续更新中…关注微信公众号LearnJava：一起学习，一起进步！skr~