索引的威力
为数据建立索引是提高数据库访问性能的重要手段。因此，为数据表建立正确的索引至关重要。如果你的表不是很大的话，那么没有索引可能感觉不到什么。但是当表的规模达到一定程度，好的索引将会使查询效率提高几个数量级。
小编曾经在工作中遇到过这样的问题，即对数据库进行某些操作会耗时长达8天之久。在对其中耗时最长的几个query进行分析之后，我意识到建立索引会使性能得到优化。最终的结果是，索引使得总耗时从8天降为了2个小时。
举个栗子
有很多书（特别是英文书）的最后，都会有索引（Index）部分。每一行索引由一个关键词和一个页码组成。关键词按字母顺序排列。如果读者对书中的某一个词感兴趣，可以方便地找到索引项，然后直接翻到对应的页。
假如没有索引的话，那么如果我们要查找某个词出现的位置，必须把书从头到尾翻一遍。这样的效率是很低的。
扑克牌
假设你有一副不包含大小王的牌，一共52张，牌是顺序是随机的。现在让你从中找到红桃8。最简单的办法是从第一张开始一张一张翻过去，直到找到为止。从概率的角度来讲，你平均需要翻一半的牌，也就是26张。
现在我们换一种玩法。我们将4种花色的牌分开，分成4堆，每堆13张牌。牌堆的顺序和每堆中牌的顺序都是随机的。现在再让你去找红桃8，正确的做法应该是先找到红桃那一堆牌（需要平均找两次），然后在那13张牌中顺序地找（平均需要找7次）。所以总的查找次数就变成了平均9次。
更进一步，如果我们将每堆牌再分成两份，A~6一堆，7~K一堆，平均的查找次数将会降为6次（想想这是为什么？）。
这就是数据库索引的工作原理。通过将数据按键值进行分类和排序，可以大大提升查找数据的速度。
B+树
数据库通常采用B+树作为存储索引的数据结构。B+树的原理非常简单，它也是将键值分成许多小的子集。每个子集就是B+树中的一个节点。节点之间通过树状结构进行组织。最重要的是，节点之间遵循B+树的规则，即左子树中的键值 < 父节点中的下一个键值 < 右子树中的键值。这使得键值的查找可以非常的快速，因为我们避免了搜索大量的数据，而是把搜索范围缩小到一个相对很小的范围。
比如，在这棵B+树种，为了找到键值16，我们从父节点中的第一个键值40开始：
1. 由于16小于40，所以向左分支搜索；
2. 由于16大于10但是小于30，所以向10和30之间的分支搜索；
3. 找到16；
可以看到，B+数的搜索次数与树的高度是密切相关的。因此，如何保证树中没有特别长的分支至关重要。这需要在增加，删除、更新等操作的过程中，通过特定的算法来尽量保证各分支的高度基本一致。
事实上，B+树是一个非常复杂的话题，并非只言片语能够讲清楚。感兴趣的小伙伴可以参考各种算法类书籍。
好了，简单的讲解就到这里。欢迎与大家进行深入的讨论。
关注并私信小编，可获《高性能MySQL》、《算法导论》等高清原版电子书。
