CMU 15445 7.skip list + radix tr

https://15445.courses.cs.cmu.edu/fall2018/notes/08-trees2.pdf

1. 索引其他

主要内容为，隐式索引，局部索引，索引覆盖，索引包含，函数索引。

索引不一定要显式创建，也有dbms自动为你创建的时候，比如primary key, foreign key, unique key。

局部索引，也就是不为整个表去建索引，索引可以基于表的子集。优点是减少索引的大小。

image.png

索引覆盖，也就是要查找的列都在建的索引里，这要就不用额外的去原数据集里查找索引里没存储数据的列。

image.png

有的时候，创建索引 但不需要把这一列加到索引里，但是又不想去原数据集里查出这列的数据。这时就需要下面的技术。

image.png

函数索引。
http://database.51cto.com/art/201010/231096.htm

2.跳表

跳表的查找，插入，删除 ppt里说的很详细了。

image.png image.png image.png

跳表的优点，相比b+树他更节约内存，他不需要rebalance。
缺点，对缓存不友好，因为是链表的关系。其次就是反向查找不方便。

3.radix tree

image.png
image.png

几大数据结构性能比较

image.png

倒排索引

传统的索引，都是通过一个列找信息。倒排索引，是一种全文索引，是看哪些文章包含这个单词，传统的索引没法hold住整个文章的内容。搜索引擎是最常用到这个技术的。

image.png

对这个有兴趣的，可以学习这门课
Inverted indexes are covered in CMU 11-442.
https://boston.lti.cs.cmu.edu/classes/11-642/