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/
网友评论