闪存数据库的索引是数据库特有的一种加快查找的方法，这种方法可以 有效的提高数据库查询的性能，基本上每一种数据库都会有索引的功能，那么索引的带来的额外的元数据开销也是非常大的。
目前的索引组织的数据结构都是按照磁盘的特性，用来设计对应的数据结构，当底层的存储介质换成闪存之后，传统的索引的数据结构可能就不太实用了，因此需要去设计面对闪存的数据库的索引。
1、闪存的存储特性，在传统数据库的索引上会有哪些影响，传统的数据库索引的设计会带来哪些问题
传统的数据库的设计大都采用了B树或者B+树，这种数据结构由于索引的更新，对于传统的磁盘可能影响不大，因为是使用本地更新，更新索引之后的地址是不变的，那么其他索引指向的指针不需要发生改变，但是当存储介质变成了闪存之后，闪存支持异地更新，那么更新的索引值会有其他的地址，那么连带的反应，其他指向的这个节点的索引节点都是变换，产生一个扩散的效应。因此会造成闪存更多的写操作，所以，对于针对真诚的特性设计相应的索引结构。
2、传统的数据库的索引主要有两种数据结构来组织，一种是B树，一组是B+树，这两种数据结构的区别是什么呢？
对于B树来说，每个节点都存储三个信息，一个是索引值，另外一个是该索引值对应的数据记录的地址指针，还要一个位置指针，指向下一个节点。
B树的查找过程：
首先索引在B树进行查找，从根节点开始一层一层的查找，找到一个对应的节点，然后从这个节点中取出对应索引的数据指针，从这个指针找到对应的数据。
B树的插入过程：
如果要插入一个记录，实际就是插入一个索引，这个时候，选择一个合适的叶子节点进行插入，如果插入叶子节点但是叶子节点超过了一个页的大小，这个时候将这个叶子节点进行分裂，取一个节点到上层的父子节点，如果父子节点还是满的时候，继续分裂，知道根节点，最坏的情况是在产生一个根节点。
B树的删除过程：
如果要删除某个记录，即要删除对应的索引，这个时候，如果要删除的节点不在叶子节点上，这个时候将这个节点和后继的节点交换位置，然后删除这个节点。在叶子节点则直接删除，如果删除之后，这个节点的索引的个数小于页的一半，这个时候，可以进行合并操作，将左右的兄弟节点进行一个合并操作。
B+树
对于B+树来说，B树显然只能进行随机的查找，对于顺序的查找，还是得从根节点开始继续查找一个路径。B+树则不同，B+树能够进行随机查找，同时能够支持顺序查找。
B+树是在B树上进行了改变，首先，B+树中包含两类节点，第一类节点是非叶子节点，第二类节点是叶子节点。对于非叶子节点，都可以看成是索引指针，起着指针连接到叶子节点的作用，用来快速定位某个叶子节点。对于叶子节点，包含了记录的索引值，和指向记录的指针，和指向下一个叶子节点的指针，叶子节点本身按照键的大小自小二大的顺序链接。
对于顺序查找，直接在叶子节点，按照索引的顺序从小到达的遍历查询即可
对于随机查找，按照主键的索引值，从根节点开始查找，如果没有则通过非叶子节点的指针指向下一个层，直到查找到叶子节点，确实是否存在，记住对于B+树来说，随机查找都是从根节点查找到叶子节点的。
插入操作：插入一个数据时，首先还是需要从根节点查询到叶子节点，找到插入的叶子节点的位置，然后在在这个叶子节点进行插入索引，如果叶子节点空间不够，则进行分裂，如果叶子节点空间够，则直接插入。
删除操作：删除一个数据时，同样首先找到叶子节点，因为所有的数据都存在叶子节点上，所以必须得去找到叶子节点。然后如果叶子节点比较少，这个时候会发生合并操作，然后删除。
3、了解了B树和B+树的基本知识后，对于传统的B、B+树的索引结构，迁移到闪存上有哪些问题，目前有哪些改进的方法？
B树存在的缺点：
B+树存在的缺点：
同样，B+树在叶子节点的更新增删，都会产生扩散的影响，造成多次的闪存写操作，代价较大。
4、对于索引的各种改进的方法
对于B树
一种基于日志的B树索引方法的体系架构BFTL
对于B++树
惰性更新B+树
FlashDB
对于直接更改整个数据结构，重新其他的树结构
FD树
LA树
下面对5种改进方法做一个简单的总结。
5、一种基于日志的B树索引方法的体系架构BFTL
基本思想：
简单来说，他的思想是因为B树的节点更新带来大量的扩散性更新，那么采用日志的方法，将这些更新通过一个缓冲区，保留这些记录，让这些记录通过缓冲区，减少写到闪存的更新写的次数。
当缓冲区被记录塞满的时候，这个时候就需要替换出去，BFTL为每个记录都设置对应索引值，将索引单元拼凑成为一个页，那么对于同一个物理节点的数据，可能更新的记录存放在不同的物理页上，通过一个转换表去记录存在哪些物理页上。在执行B数的查询时，首先查找转换表可以直接查询到每个闪存物理页对应的B节点的最新值，这样不用去遍历闪存。
具体实现：
优点：
缺点：
6、惰性更新B+树
传统的对B+树的更新，都是在缓冲区缓冲一部分预读出来的节点，这样不用总是去闪存上读节点，但是这样受限于缓冲量，并不能减少太多读写操作。
惰性更新B+树的基本思想：
思想比较简单，就是设置一个惰性更新池，对所有节点的更新操作，都不直接更新，而是直接写入到这个更新池，在更新池中对请求进行合并去掉冗余，然后当更新池满了之后，触发一个提交操作，批量的写入到闪存中，并行更新B+树的结构。
具体实现：
优点：
优点很明显，通过惰性缓冲区，进行批量的更新操作，减少了更新的写操作，从而对闪存的写操作减少，提升写性能。
7、FlashDB
基本思想：
思想并不难，主要思想是，节点写入的方式不一样，一种是以页写入，一种是以日志写入，前面在数据库存储管理器优化中提到过，以页写入，写性能差，但是读性能好；以日志写入，写性能好，但是读性能差，那么FlashDB就是通过对负载进行感知，动态的调整B树的节点，在不同的负载下达到一个最优。
具体实现
优点：
采用日志写的方式可以通过批量写，减少写入的次数，解决闪存普遍存在的问题。同时可以通过负载感知，来切换节点的类型，可以到达最优解。
8、FlashDB
基本思想：
具体设计
9、LA树
之前的对B+树的优化都是通过日志批量写入的方式，这种方式有效的降低了写操作的代价，但是同时，增加的读操作的代价。LA树区别于之前的这些方法，提出了一种新的面向闪存的数据结构，采用了惰性更新技术。
基本设计思想
具体实现
思想：实际是通过一个多级的缓存，延时更新操作，最后当更新操作推送到了叶子节点层，这个时候将同一个叶子节点的索引一起更新，这样不会增加额外的更新写开销，从而减小更新写这个问题。
10、总结
所以总的来说，索引需要解决的就是异地更新，读写代价不一致导致的大量的更新写的问题，基本解决的办法都是通过设置缓冲区，不管是多层还是一层，缓冲区来记录日志，将更新写推迟写入到闪存上，最后批量写入对一个页的更新，合并更新，通过这种方法减少更新写的次数。
那么优化的方法，可以在传统的B树或者B+树上优化，也可以自己建立一个新的数据结构，LA树