倒排索引与数据库索引
数据库索引
mysql索引以B+树作为存储结构，B+树的主要特点是，非叶子节点不存储数据，数据只存储在叶子节点上，并且所有叶子节点组成有序链表
主键索引（聚簇索引）
假设我们的表结构如下
CREATE TABLE `users` (
`id` int(11) NOT NULL AUTO_INCREMENT COMMENT '主键',
`name` varchar(20) DEFAULT NULL COMMENT '名称',
`bank_no` varchar(20) DEFAULT NULL COMMENT '银行卡号',
`hobby` varchar(20) DEFAULT NULL COMMENT '兴趣爱好',
PRIMARY KEY (`id`),
UNIQUE KEY `user_bank_no` (`bank_no`,`name`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8
数据库主键索引对应的文档存储的表内容可表示为：
| DocumentId | name | bank_no | hobby |
|---|---|---|---|
| 1 | 鲁智深 | 6201 | 篮球、唱歌 |
| 200 | 吴用 | 5100 | 篮球、旅游 |
| 3000 | 花荣 | 1234 | 台球、旅游 |
| 5000 | 柴进 | 2245 | 唱歌、游泳 |
| 5001 | 武松 | 5678 | 篮球、游泳 |
| 5200 | 杨志 | 1345 | 游泳、台球 |
| 8000 | 宋江 | 9987 | 唱歌 |
| 10000 | 卢俊义 | 3347 | 足球、旅游 |
主键索引的存储结构如下
图：主键索引存储结构
非主键索引
非主键索引存储结构
非主键索引的叶子节点只存储索引字段及主键，如果需要索引字段之外的信息，则需要根据主键再回表查询。
比如我们按照银行卡号查询用户名、兴趣爱好等字段，则会根据索引过滤后再回表查询完整信息，被称为是索引下推。
倒排索引
数据库索引是一种正排索引，上面的例子中，如果查询兴趣爱好为“游泳”的用户信息，则会触发全表扫描。这种情况下创建全文索引可很大程度的提高查询效率，而全文索引(full inverted index )就一种倒排索引(inverted file index )的实现。
如果是倒排索引，则文档存储的表内容可表示为：
| Number | text | Documents |
|---|---|---|
| 1 | 篮球 | 1，200，5001 |
| 2 | 唱歌 | 1, 5000, 8000 |
| 3 | 旅游 | 200, 3000, 10000 |
| 4 | 台球 | 3000, 5200 |
| 5 | 游泳 | 5000, 5200 |
| 6 | 足球 | 10000 |
全文索引不仅可以存储文档的ID，还可以存储单词在text的位置信息(position)
| Number | text | Documents[(DocumentId: position)] |
|---|---|---|
| 1 | 篮球 | (1: 1)，(200: 1), (5001: 1) |
| 2 | 唱歌 | (1: 2), (5000: 1), (8000: 1) |
| 3 | 旅游 | (200: 2), (3000: 2), (10000: 2) |
| 4 | 台球 | (3000: 1), (5200: 2) |
| 5 | 游泳 | (5000: 2), (5200: 1) |
| 6 | 足球 | (10000: 1) |
最后，倒排索引作为一种索引结构，可以更好的定位数据，并能扩充一些搜索特性，但是也会占用更多的磁盘空间。
作者:那些年搬过的砖
原文链接:https://www.jianshu.com/p/d54f33addaea