正如我们看书需要目录，因为可以加快寻找内容的过程。数据库的索引，solr和es用到的倒排索引，都是为了加快获取数据的速度。
一 常用索引数据结构
1.1 数组
常用的内存里面的索引数据结构有数组，哈希表，树等。先说数组，数组可以说是编程接触到最早的数据结构了，优点是简单，支持快速访问，可以根据index快速访问数据，并且数组在一般的编程语言中，在内存里面是顺序存储的，所以具有内存访问的局部性优势（即cpu从内存中获取数据的时候，并不是只取需要的数据，而是取一块数据同时放入缓存），这样下次访问数组的其他数据的时候，数据很大的概率已经在缓存中了，不用再去内存获取了。
这种局部性原理也有缺点，就是造成伪共享问题，所谓的伪共享的问题，就是两个变量在内存中本来是在程序中没有共享的，当时由于内存存储的位置比较近，一个线程读取A变量把B变量也读进了同一个缓存行中，那么如果B变量被另一个线程修改了，整个缓存行都失效了，也影响了A变量的缓存了。
有些程序优化的比较厉害的话，用到一些填充字符或数组，目的是保证中间变量是在一个缓存行中，不会因为其他变量的原因让其失效，解决变量伪共享的问题，比如：Disruptor 高性能队列。
我们在搜索数据的时候，有时候并不是做等值查询，有时候是做范围查询，数组可以很好地支持范围查询；当然数组也有比较明显的缺点，就是不支持高效的插入和删除，只适合存储静态的数据。
1.2 哈希表
哈希表是数组和链表结合的产物，利用高性能的分布均衡的hash函数结合数组的快速访问特性，迅速定位一个槽位，接着通过链表的遍历来解决哈希冲突的问题。如果单纯利用链表的话，如果负载因子比较大，就会导致性能的退化，所以JDK1.8以后的hashmap在链表长度大于8 的时候，将链表转成红黑树，以提升查询的性能。
哈希表的槽位的定位是根据hash函数计算的，所以没有顺序而言，所以哈希表这种数据结构不便于做范围查找，在实际的使用中，其实哈希表的遍历也挺麻烦的，因为不是所有的槽位都有值，和负载因子有关。
1.3 树
树这种数据结构也非常常见，比如二叉搜索树，左边的树存储的数据小于根节点，根节点数据小于右边树，性能比较均衡无论是查找还是插入时间复杂度都为O(log(n))。数据库的索引不能采用二叉树这种数据结构，原因是数据行很多的话，如果用二叉树，树的高度会很高，层高的话，不可能所有的数据都存储在内存中，有大部分数据就存储在磁盘上，这种指针访问是对磁盘的随机访问，数据访问就会很慢。既然二叉不行，是不是可以用多叉树的方式那，就是一个根节点可以有多个子节点，比如InnoDB引擎中索引的多叉树，多达1200个子节点，三层可以存储数据为120012001200为17亿行个数据，每层的数据都是按照从顺序排列，这样便于我们做范围查询。
二 InnoDB索引
InnoDB索引采用上面说的多叉树方式存储，InnoDB是索引组织表，表数据就是存在聚簇索引上的，即主键索引上的，索引的非叶子节点存储的是主键，叶子节点存储的数据行；而非聚簇索引，非叶子节点存储的是建索引字段的值，叶子节点存储的是主键，按照极客时间的Mysql的例子举例：
mysql>
create table T(
id int primary key,
k int not null,
name varchar(16),
index (k))engine=InnoDB;
插入如下数据：
(100,1)、(200,2)、(300,3)、(500,5) 和 (600,6)
如下表将形成如下的表结构：
图来自极客时间
主键中叶子节点不是一个节点存储一行数据，是一个节点标识一个数据页，一个数据页里面保存多条数据记录。
图中的主键索引即ID的索引，叶子节点R1，R2等是整行记录。
另外一索引树k，叶子节点存储的是主键k的值，我们查找数据的时候，如果根据主键去查找，就直接在主键这树上查找即可以了。如果我们通过k值去查询的时候，我们先找到对应的主键id，再通过主键id到聚簇索引上去找到对应的记录，这个过程叫做回表。
索引查找就是这样子，那么数据会不断增删，那么索引树也需要维护，将一条记录插入到索引中的时候，如上图，如果id值为700，则直接再600后面添加即可；如果插入是400，需要挪动500和600空出空间，如果600这个id对应的数据页又满了，那么就会发生分裂。相反删除数据之后，如果相临的数据页的空闲空间都大于了一半，那么就会产生数据页的合并。
所以要先插入数据的性能高，id最好是顺序增长的，这样，就减少了数据的挪动，只要在后面增加就可以了，所以这就是建议用递增的id的原因，另外如果用一个长字段作为索引，那么普通索引由于要存储主键的值，所以普通索引的体积就会增加。
所以一般不建议用业务字段作为主键。
好了，下次再聊。
网友评论