1 索引数据结构

        数据索引的结构有很多种,下面将会介绍以下几种：

    1.1 hash结构。

            hash结构是将数据通过key-value的形势存储数据的。这种方式存储数据对于等值查询来说数据非常快，但是不适用于做范围性的数据查找。因hash结构的数据存方式是键值对，所      以等值查询的方式很快，时间复杂度是o(1)。

    1.2  查找二叉树

             查找二叉树是将数据通过以二叉树的形式来存放的，左子树的数据必须要小于根节点，右子树的数据必须要大于或者等于根节点。二叉树的方式查找的时间复杂度是log2为底N            为对数。 但是查找二叉树的缺点就是一旦根节点没有选择好，就会出现左右高度不平衡的现象，极端情况会退化成一个单链表。下面将通过几张动图来表示下查找二叉树的几种情况。
    假设数据库中的数据有 1,3,5,7,9,11,12,13,14,15,16,17,18,19,20   ：
    当索引数据存储在查找二叉树中的时候，最理想的情况下是左右两边树高度一样，且左子树小于根节点，右子树大于根节点：

查找二叉树最理想的情况

            但是查找二叉树有时候会出现比较极端的情况：情况如下：

查找二叉树最不理想的情况

     1.3 平衡查找二叉树     

               查找二叉树在极端情况下会退化成一个单链表，但是这个单链表的情况是非常不理想的，于是平衡查找二叉树便孕育而生。 二叉平衡查找树要求在查找二叉树的基础之上根节         点的左子树与右子树的高度相差必须小于等于1，这样二叉平衡查找树有了查找二叉树的优势。但是二叉平衡查找树随着数据的不断增加树的高度也会在不断增加，查找的时间复杂         度也在不断的提高。针对1.2的二叉树数据：得到平衡二叉树如下图：
                

这种是属于平衡二叉树最理想的情况

                  平衡查找二叉树最不理想的情况如下图所示：

平衡二叉树嘴不理想的情况

                     如上图所示，平衡二叉树最不理想的情况下，左子树比右子树的节点高度小1，但是这种情况也比二叉查找树的情况好得多。平衡二叉树的查找时间复杂度一般都是树的高              度，通过上面的介绍，如果数据量特别大的时候，按照这种树的情况的话树的高度也会特别的大。从而时间复杂度相对也比较大。针对于这种情况，于是出现了B树。

        1.4 B树

                        B树是在二叉平衡查找树的基础之上演化而来的一个多叉平衡查找树。这样在二叉平衡查找树的基础之上可以降低树的高度。B树的数据结构图形如下：
                        

B树结构

                        B树的结构里面每一个节点都存放了其对应的数据，这样，根节点下有多个子节点，可以大大降低其树的读，而且对于等值查询的sql，取数据也比较快，但是对于范围查                  询会出现回溯现象，比如查询小于12的数。查完5的根节点之后又要回溯到13的根节点下去找，这种结构对于范围查询的话效率就不是很高。
            

         1.5  B+树  

                       B+树是在B树的基础上演化而来，其数据结构如下：
        

B+树结构

                    B+树只有叶子节点才存放数据，根节点存索引值。叶子节点由一条双向链表链接，这样对于等值查询及返回查询都有不错的效率。