注意注意 LitePal 3.2来了，千呼万唤的索引功能
各位小伙伴们早上好。
上周六的上海GDG Android 11圆桌会议活动虽然在一开始的时候出现了一些声音的小状况，但最后还算是圆满结束了。Yigit Boyar大神对这次活动中提出的问题给出了高度的评价，我还是非常开心的。
888888888.png
本来打算在今天的文章中贴出圆桌会议活动回放的链接，但是到目前为止回放还没有提供出来，所以想看回放的小伙伴们只能再多等等了。也可以时不时去刷一下上海GDG的bilibili主页。
回到今天的主题。目前我手上正在维护的开源库主要是LitePal和PermissionX这两个，属于交叉维护的状态，升级完了这个就抓紧去写另外一个。其实今年我本来还准备再写一个新的开源项目，但是现在不知是否还能够抽出足够的时间，思路已完备，就是迟迟没动手。
LitePal自上次3.1版本支持了事务之后，基本数据库该有的功能差不多都具备了，但是长久以来，始终还有一个呼声，就是有些朋友希望LitePal可以支持索引。
关于索引这个功能，我在做LitePal 1.x版本的时候就考虑过加入，当时代码写了有一半左右，但是由于测量下来结果不理想，最后又移除了这部分功能。为什么不理想呢？因为在移动设备的数据库上，索引其实并不能起到什么太大的作用，只有在数据量非常大的时候，索引才能体现出查询效率的优势，而移动设备通常都不会有非常大的数据量。
但是不支持索引，最后可能会成为我的一块心病，因为时不时就会有朋友要求LitePal支持这个功能。所以我决定，在LitePal 3.2版本中加入对索引的支持，补齐这块功能缺失。同时这也是3.x系列的最后一个版本，下个版本将会有较大的架构变动，LitePal会逐渐向Room的设计与用法靠齐。
另外，我要提醒大家的是，虽然LitePal 3.2版本支持了索引，但是我认为绝大部分的朋友还是不应该使用它。因为第一，你真的用不到它（后面会解释为什么）；第二，怕你用不好它（错误地使用索引反而会降低效率）。所以，当你真的清楚自己在做什么的时候，请再使用索引。
读到这里，是不是有小伙伴觉得我一直在劝退？没错，但是并不影响你阅读本篇文章，因为了解一下什么是索引也是挺好的，即使你用不到它。
/ 什么是索引？ /
简而言之，索引是一种用于加快数据库查询的工具。
在我们传统的印象中，数据库的查询速度都是非常快的，通过一条SQL语句在数据库中查找满足指定条件的数据几乎是瞬间就可以完成的。
那么你有没有想过，数据库是如何从海量数据当中找出那些满足指定条件的数据呢？
其实并没有什么特别的技术，就是将数据库表中所有的数据全部都查询一遍即可，也就是所谓的全表搜索。
听上去有些让人不敢相信，但事实确实是如此，只不过得益于数据库本身高效的执行效率，所以查询速度通常都非常快。
在SQLite中，想要知道你的查询语句是否是全表搜索，只需要在你的查询语句之前加入explain query plan关键字即可，如下图所示。
888888888.png
可以看到，detail这一栏当中的信息是SCAN TABLE Song，这就意味着SQLite将Song这张表全表都搜索了一遍。
这种全表搜索的方式只要是正常人的思维都知道是有问题的，因为随着表中的数据越来越多，全表搜索的时间也注定会越来越长。比如说像淘宝这种拥有几亿用户的数据库表，如果我每次登录都需要将这几亿条用户数据全部搜索一遍，从中找出我登录的那个账号，这显然是不切实际的。
那么如何解决这个问题呢？为了能够从海量数据当中快速找到指定的数据，所有的主流数据库都会提供索引这个功能。
索引的工作原理说简单也简单，说复杂也复杂，那么我尽量往简单的说。简单来讲，索引的工作原理本质上就是二分查找。
二分查找是一种很神奇的算法，它可以将查找的时间复杂度降低一个量级，从而显著地提升查询效率，但前提是要求数据必须有序。
举一个形象的例子，假设一个数组当中有20亿条数据，我想要在这个数组中找到其中某一条数据，如果使用遍历查询的方式，那么最坏情况下需要查询20亿次才行。
而如果使用二分查找呢？我们可以每次取中间值，然后舍弃不满足条件的那一半数据，重复进行以上操作，这样最多只需要查询31次就可以找到结果。
888888888.png
有没有被这两个不同的量级吓到？
不过数据库中存储的是非常复杂的关系型数据，是不能用简单的数组来表示的，并且维护一个有序的数组本身就是一件成本很高的事情。
这个时候就需要引入另外一种高级数据结构了：二叉搜索树。二叉搜索树是一种树状的数据结构，它由根结点、左子树、右子树三部分组成，并且左子树的值总是小于根结点，右子树的值总是大于根结点
888888888.png
有没有发现？二叉搜索树也是可以运用二分查找特性的，因为它每次也可以舍弃一半不满足条件的数据。另外，维护一个二叉搜索树并不像维护一个有序数组那样成本很高，因为已经有很多现成的解决方案了，比如我们所熟知的红黑树。
然而二叉搜索树的方案仍然不适用于数据库索引，主要是因为索引并不只是存储于内存当中，还要存储在硬盘当中。而硬盘的存储是分数据块的，不同数据块之间的磁盘读取也是比较耗时的。假设我们使用二叉搜索树来作为索引的存储结构，那么树的高度就会很高，从而使用索引查询时为了读取数据可能要跨很多个磁盘的数据块，导致查询效率降低。
因此，为了降低树的高度，几乎所有主流数据库都是使用N叉树这种数据结构来建立索引的。N叉树和二叉树类似，只是它的每个根节点可以有多个子树，而不像二叉树那样限定只能有两个。
根据我查询到的资料，MySQL使用的N叉树（准确讲是B+树），N大概是1200左右。我们可以试算一下，1200的三次方大概是17亿，也就是说N叉树的高度只需要3层，就可以存储二叉树将近31层的数据。这样就在内存查询效率和磁盘查询效率之间找到了一个比较合适的平衡点。
虽然不同数据库在具体的实现方面还会有些不同，但大体的思路都是差不多的。
/ 索引的用法 /
了解了什么是索引之后，接下来我们看一下索引的具体用法。
索引的用法是非常简单的，至少在LitePal当中索引的用法非常简单，毕竟LitePal当中一切都非常简单。
如果你想要给一个字段添加索引，只需要在该字段的上方加上一个@Column注解，并指定index = true即可，如下所示：
888888888.png
然后升级一下litepal.xml当中的版本号，这样LitePal就会自动给Song表的name字段加上索引。
没错，这样就OK了。虽然为了支持索引这个功能我着实编写了不少代码，但是对于使用者而言，你所需要做的就只有这么多。
现在我们可以再使用刚才的explain query plan关键字，来检查一下同样的查询语句：
888888888.png
可以看到，detail这一栏中的信息和之前不一样了，说明现在我们的查询语句已经不是全表搜索了，而是会使用索引来加速查询。
/ 索引的效果 /
那么使用了索引之后，效果到底如何呢？说实话，想要验证索引的效果确实是不容易的，因为在移动端我们通常根本就没有海量的数据进行验证。
但是没有经过验证的索引功能是没有说服力的，所以我还是尽可能想办法把验证的结果展示给大家。
既然没有海量数据，那么就自己造呗。
LitePal的存储效率其实还是比较不错的，借助LitePal.saveAll()方法，存储10000条数据耗时大概在700毫秒左右，只需7秒时间我就可以模拟出10万条数据。代码如下：
888888888.png
那么就先用10万条数据来进行测试吧，首先检查一下Song表中的总数据量：
888888888.png
是10万条，准确无误。
然后使用如下查询代码从这10万条数据当中查找指定的数据
888888888.png
结果如下图所示。
888888888.png
可以看到，借助索引，我们在10万条数据当中查询指定数据只需要6毫秒，这个效率可以算是相当不错了吧？
那么如果不使用索引，全表搜索的情况下查询需要多久呢？我们同样来试一试。
lyric这一列是没有添加索引的，现在我们根据这一列作为条件进行查询，那么就会进行全表搜索，代码如下所示：
888888888.png
可以看到，总耗时是23毫秒。
虽然23毫秒是6毫秒的4倍左右，但是对于移动设备而言，23毫秒并不是很长的耗时，基本上在你完全感知不到的情况下查询就结束了。
并且这是10万条数据，通常我们在数据库表当中存储的数据还远远到不了10万条，这样索引能带来的性能优势会进一步减少。
当然我们都知道，随着数据量越来越多，索引的性能优势也会越来越大，但是即使我将数据量放大到了100万条，全表搜索的速度仍然还是很快，基本都可以在150ms左右的时间完成。
这也是为什么LitePal长期以来不支持索引的原因，因为移动端真的存储不了那么多的数据，即使加入了索引，所能带来的性能提升也非常有限。
但是如果表中存储的数据量真的极大，那么是一定要用索引的，所以这项技术在服务器端的数据库当中使用得相当普遍。
秉着严谨的态度，我又将表中的数据扩大到了1000万条。这个量级的数据已经不是很好模拟了，我存储这些数据就花了十几分钟的时间，而且还要保证手机存储空间充足，1000万条数据可能会占用1G左右的空间（不同手机会有差异，我在另外一台手机上测试是700M的空间）。
888888888.png
这种数据量级下，我们先来试一试借助索引的查询速度：
888888888.png
仍然很快，10毫秒的时间就可以将数据查询出来。
那么不使用索引呢？我们也来试一下
888888888.png
这个对比差距就比较大了，不使用索引的情况下，1000万条数据全表搜索会耗费2.5秒的时间，这是一个足够长到让用户能够明显感受到卡顿的时间了。
所以，像服务器的数据库当中动辄可能会有几亿几十亿的数据，这个时候是必须要使用索引的，而移动端可能很难想象会有这种数据量级的场景。
/ 到底应不应该使用索引呢？ /
写到这里，我们已经把什么是索引，LitePal中索引的用法，以及索引实际的效果全部都分析完了。
那么最后还剩一个问题，就是我们到底应不应该使用索引？
其实应不应该使用要看你到底用不用得着，我的个人看法是绝大部分人应该是用不着的，因为移动端的数据库几乎不太可能会存储这么多的数据。而在用不着的情况下强行使用索引，反而可能会降低你的其他数据库操作的效率（比如增删改），因为维护索引的B+树也是需要耗时的。
另外，添加索引的列尽量要保证数据重复率非常低才行，不然索引将会失去效果。这个也很好理解，比如我给性别这一列加上索引，由于性别就只有男女两种，1000万条数据我可能要查询500万条才能把指定性别的所有数据查询出来，这种索引基本是没有作用的。
而如果你对索引本身就已经非常熟悉了，并且完全清楚自己在做什么的时候，请放心使用索引，LitePal已经完全为你准备好了。
/ 如何升级 /
升级的方式很简单，只需要在build.gradle中修改一下配置即可：
888888888.png
3.2.0版本中的所有的功能都是向下兼容的，因此你的升级不用付出任何成本
另外，本篇文章是写给已经有LitePal基础的人看的，帮助他们快速了解3.2.0版本的新特性
