开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第七课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15863
第七课（一）
内容介绍：
一、指针混写
二、虚拟存储器
三、索引
四、无序索引
五、稀疏索引
六、有序索引
七、稠密索引
八、多级索引
九、索引更新
十、辅助索引
一、指针混写
指针混写实际上说是持久指针到内存指针的一个转化。
面临问题的几个问题，一个就是外存指针外层空间大，所以的指针的长度长，内存短。假定按照换页方式，外存用48位，内存是32，32位相当于4个GB，1G 正好是30位，4G 正好32位。
然后我如果按页式的话，假定一个页大小是4k是12位，2的12次方，1k是2的10次方，页里头12位，这12位作为业内偏移的，前面20位是页号在内存里头可以有2的2次方，内存里有一兆多个页面，外存48位可以明显看出，页面内部也是12位，这边的话30 36，36~12就是要把这边的页号36位，另一边20位，转换就要把一个更长的转换到一个短的。
转化的方法：内存指针是记录在内存里的位置，另一个外存，转换基本方法就是一个转换表，转换表有两项，一项是外存的地址，就是页号的地址，不用页内地址，就不用全部地址，假定按4k为页，20位是内存的页号，这边是外存的页号，指针来了以后，要到表里去查，如果在内存里头查到就给转过来了。
为什么叫混写问题，如下图：
两个记录 a 和 b，b 的条件 a 里头有一个字段，包含到b的一个指针，这个持久指针。这里就有问题，有一个指标质量 b，如果对应已经在内存里， a 里指针要把也替换成内存的指针，就用内存指针来访问过程。这个地址要把转换出来，在里头用一种方法每一次拿地址都要去查表就很麻烦。可以依次把这两个在这层转过来，叫交易转换，这就是转换的问题。就是在内存里头另外一个地方保留了一个持久指针，指向对象已经在内存里了，已经有一个内存地址，就要把内存地址替换成内存地址，但是内存的地址是一个临时的，将来有可能这个地址位置变了或者失效，对象不在内存放，位置可能给别的地方。要解决有关问题，叫指针混写。具体过程片子里有，分成两种，一种是用软件的方式来做，效率比较低，还有用硬件来做，就是有专门的寄存器来进行指针的转换，效率比较高。大家先看下一节课再讲。原理大家记住，细节当中还有一些问题，有一些比较复杂的逻辑，清楚指针转换或者叫指针的混写 swizzling 是解决什么问题的，比如外围是外存地址到内存地址的一个转换问题。
二、虚拟存储器
具体的在第四章指针的管理，一个用软件的方式来做；另外一种就是用硬件来做，实际上用到虚存的机子，虚拟存储器实际上是操作系统里的一个概念，某种意义上讲指针转化把内存当中，比如只有32位4G的内存，但是要把48位这么大空间里头外存的内容放在内存里头去。虚存就是感觉使用的有48位这么大的一块，实际上没有多，虚存主要是通过页表进行转换。虚存在存储管理操作系统里头讲，本站属于操作系统的内容，专门有一个模块负责管理内存，内核里头有一个模块。操作系统管理一个 CPU，CPU 是一个分时资源，操作系统的一个主要作用就是把物理资源转化成虚拟成一个逻辑资源，然后给用户提供。就把虚化了。
Cpu 资源只有分时多个进程，多个程序都用 CPU，用分时的方式，是 CPU 管理，就是进程管理。还有内存管理，有很多种内存管理；还有 IO 管理中段管理。操作系统一个很重要的就是硬件当中发生外界或者设备或者发生什么事情，要中断处理，都是操作系统内容，涉及到虚存。这个内容用到是虚存，里头讲了硬件做混写的时候，具体的过程。另外也举了一些例子，要看例子就知道这个过程，过程主要是在指针转换页面当中，逻辑比较复杂，中间查到分不同情况去处理。
三、索引
索引，前面讲用年龄就是中国的属相，实际上就是把年龄作为关键字，如要找一个人，有年龄线索知道他属猪的，就在属猪的那里头找，就把查找的空间缩小到1/12。假定每一个属相的人差不多，相当于把人按照年龄的属相，分成12份，每个属相的分一份。知道这个人是属猪的，就到属猪的里面去找，要查找的人就减少了，空间量缩小原来是1/12。
例1:以年龄为关键字，定义
Hash(Age)= Age Mod 12，相当于把人按年龄分成12个组即通常的12属相“鼠、牛、虎、兔，..”在同一属相中再线性搜结果:寻址效率提高12倍!更直观的例子，电影院进门的时候有两个门，不知道电影院座号怎么排的，是单双号，比如这边是单号13579，那边双号246810就是一个索引。然后影剧院一边的门写个单号，一边门写个双号，这样观众入场的时候，根据你的座号，双号走双号门，单号走单号门，这就是一个索引。入场找座位的时候，通过这个机制，要找个座位的空间只有原来一半，带来的好处就是观众入场的时间，找座位的时间缩短到原来的一半时间。如剧场里有1000个座位，单双号机制，进来后双号到双号这500人去找，单号到单号的500个找，没有单双号意味着进来要在1000个里面找。相当于做一个模，模二，就是单号还是双号，双号模块是0，单号模块是1。
例2:影剧场分单双号进门，相当于Hash(N)=N Mod2
观众的入场的找座位的速度就提高了一倍，其实所有的索引跟这个原理是一样的。
索引的原理本质是把信息按照某些属性信息做一个分类，把分分分成很多类，每一类划成一小份，知道要找的东西是属于哪一类的，就到那一小类里去找，不用整个漫无目的的找，使得提高精准度。英文字典也是这样，按照第一个字母 ABCD 排，英文字典有指印的， a 在书角上会弄一个半角出来，上面有个 a 然后 bcd 排，要查一个单词的话，比方一个单词是以 b 开头的，直接到 b 这个地方开头去找，这样只要找这 b 和 c 之间，这中间翻就是相当于原来的1/26，就假定，当然实际可能不一定准确，因为统计一下英文字母当中不同的开头的可能还不一样，但是大致是这样的，相当于原来的1/26。
例3:在英文字典每个字母开始处贴一标签，相当于
Hash(WordStr)= WordStr[0]
四、无序索引
无序索引就是从关键字到记录号做一个预算，所以文件没有排序，这就叫无序作用。平均查找速度就是总关键字数目的1/2，假定是一个找到为止，那大概是的1/2。由于索引文件比主文件要小一个甚至两个多个数量级，所以可以全部或大部分读入内存，内存当中搜索定位这样提高搜索，就相当于小无序管大有序。
最典型的例子就是图书的目录，看书的时候，书的前面除了封皮，标题，书名，作者和出版社的信息。什么数据库原理，然后张三李四编著，底下什么出版社，清华大学出版社什么人民出版社，人民教育出版社，再翻过来目录第一章，第一章后面写个1，知道第一章从第一页开始写，然后第二章标题是什么内容，比如数据模型后面25，就知道第二章在25页，这就是一个典型的缩影。
例:一本书的目录可看成是无序索引映射 IndexMap:
章节名称集合一>页码集合
由章节名字集合和页码集合，但是实际上这里举个例子不是很漂亮，目录的索引有序的，一般是按章节顺序排的，而且物理顺序跟章节顺序是一样的，也就是第一章他在物理顺序上排在前面，第一章在第二章前面，第二章在第三章前面，一般是这样子的，这是图书目录。读到一本书可能有200页300，但是的目录可能只有两三页，最多四五页，目录做的细，抽的关键字就越多，占子空间大。顺序索引就在无序索引基本上增加一个，索引是按照关键字来排序，查找的时候就可以用二分法，从正中间去比对一下，比大往左边，比小往右边。这样的话按照二分查找，一次可以批出一半，然后再到中间再去批一半，所以的查找复杂为：Log2(N)。比如100万，用折断查找比顺序扫描一遍肯定效率提高很多，当n大于30的时候，效益很理想就有效益了。顺序索引又分两类，也就是小有序管大有序和小有序管大无序，对所有的文件是有序还是无序，又分了又分了两类。
