开发者学堂课程【高校精品课-西安交通大学-数据库理论与技术：第七课】学习笔记，与课程紧密联系，让用户快速学习知识。
课程地址：https://developer.aliyun.com/learning/course/12/detail/15863
第七课（三）
内容介绍：
一、指针混写
二、虚拟存储器
三、索引
四、无序索引
五、稀疏索引
六、有序索引
七、稠密索引
八、多级索引
九、索引更新
十、辅助索引
八、多级索引
多级索引就是说一个主索引可能放不下，占的空间太大，就可以减索引的索引。一级不行二级，二级不行三级，就变成多级索引。索引就分为外索引，就相当于主索引的系数索引，内索引就是主索引文件这样分两级。如果外索引仍然太大不能放入内存，可以再建一个索引，这样就可以一层层的就变成了多级索引。多级索引插入删除操作对相应的各级索引都要做进行操作，这就是带来的问题带来问题，这个是多级索引的例子。
这个就是外索引，查找先从一个索引开始，告诉你在第一个索引里头，然后到第二层索引告诉你再找，这是两级索引，如果再多一层，就可以三级索引，多级索引。
九、索引更新
索引更新操作第一个删除操作，删除操作就是在主记录里头就是主文件当中把一个记录删除了，在索引当中关键字对应的，索引项也要删除，主记录和索引的关系就是主仆关系。索引是一个仆人，是为主文件服务的仆人，或者叫皮包关系，皮之不存，毛就没有了，就是这样一种关系。如果被删除记录是文件中具有搜索键值的唯一记录，则索引项中的相应关键字也需要跟着被删除。
单层索引删除不讲了。对偶的插入问题，常用于新的记录、新的关键字值，如果不存在，同样在索引里头做相应调整。操作的时候还面临很多问题等等，这是关于索引的更新插入删除。
十、辅助索引
实际上就是说非关键字上的这种索引，往往是非唯一键索引，叫辅助索引。记录不一定要按照排序，所以是一个关键字值，后面这个位置用了一个集合表示等于这个关键字值可能有很多，比如班级索引，如这个班有30个学生，班级号后面那30个学生那个地址信息，这个时候利用这个索引可以快速查到某一个班的所有学生。经常需要查找的某个属性值，做的不是主索引的搜索键，满足条件的全体记录，比如像常州某个班级或某个专业或某个学生等等这样的记录查找。举个例子，按账号顺序存储的账号、数据库中希望查找某个分行的全体账户，这个账户应该是账户表。例2查找具有指定余额和余额范围的全体账户，这个都可以用辅助索引来做，都建立辅助索引。这个图是在余额上面建立的辅助索引，例子举得不是特别好。
余额做索引，书里就是这样举例，用这个方式来说，余额的350、400、500、600的，但是数值型如果再有浮点型的话，不是值很多，所以效率不一定高，这是关于辅助索引。
主索引和辅助索引，辅助索引必须是稠密索引，不能是稀疏索引。原因就是辅助索引进入的物理顺序不是按照排序的，而稀疏索引要求必须排序，没法满足排序要求，辅助索引必须是稠密索引。更新文件文件上的每个索引必须做更新，所以主文件要与时俱进，主文件变了，索引要同步跟着变，这个主要是给数据库后面的这种受处理是这样的问题。索引多提高了查找效率，但是更新效率降低，而且更新的时候又要涉及到后面会讲到锁同步的问题，会带来很多问题，当然现在不说，所以他一方面有收益，但是一方面如果要付出代价，除了空间代价以外，大家直接能看到的，因为建锁要用更多的存储空间来存放，维护代价其实很高的。可以想象我一本书我这个书有目录，书的内容电话给我增加新的章节或者章节当中有调整，标题变了或内容变了或者增加性的章节，必然目录也要同步的跟着辅助作用。word 文档可以生成一个目录，编辑一段时间，有时候发现这个内容和目录对不上，就要重新生成一次目录，给生成一个最新的，索引和一些内容是对不上的。这就是主索引和辅助索引。利用主索引做顺序扫描效率可以很高。
用的最多的一种多级索引：B+-树索引，都叫 B 树，改进的一种叫 B+树，还有叫 B*数。调查就是一个多差评的查找树，查找树在数据结构里学过的这个对应二叉树，二叉树是个查找树，中间一个关键字值左边一个值右边一个关键实际上就是二叉查找，又从结构把实现出来，用二叉树就可以实现二分查找。一个节点跟节点有一个关键字值比较一下，比小左边，比大右，然后到下一层，这是二叉树。把推广一下，关键字值个数不是一个，而是k的，比方我有10个100个，中间在2个关键词之间都有指针， 2头都有指针，就是说指针个数是关键字值个数加一，也就是我有这个关键字指针数目，下级指针数目就是加一，这叫B+树。深入介绍一下。索引顺序文件，是小有序管大有序，缺点就是会动态增长，到动态后溢出动的效率就会降低了。这个时候就引入了一种数据结构，B+树或者B数。优点用三个字，一个叫平就是平衡，另外半是空间利用是过半的，会保证半就有一半的空间是利用上的。第三个就是排序，是在动态生产当中会保持平衡。装载因子过半就是的空间节点当中有一半能够使用，另外有序。缺点就是结点分裂，就是插入的时候一个节点要拆分成两个节点，这个叫节点分裂。还有节点，如果删除的时候倒过来，节点收缩，的开销比较大，但是这个树结构利大于弊，所以是用的最广泛的一种结构。在索引当中用的最广泛的就是B+树，所以在这里要给大家介绍，B+树就是满足下列性质的数。第一个就是从叶的根节点到月节点，所有路径长度都相等的，这叫平衡。在B+树从根节点到所有的业务节点，的路径长度是一样的，这些就是平衡性。
第二条每一个非根非叶节点，除了跟节点不要求，非分的分页节点都有 n/2到 n 个子节点就半满，因为每个节点都是分叉的数，最大数那是的基数，后面会提到 n的就是的基数，比如n等于100，也就是说每一个上面可以100分有100分差，除了分节点以外，其他的非跟的非夜节点都至少保持有50个以上的分差。如果 n 等于100的话，这叫过半。第三叶子节点有多少？叶节点上有[(n-1)/2]到n-1个值，因为到叶这个节点就没有分散了，直接到了数据记录或者是到数据记录的指标，都存在到数据记录指标到业绩里。特殊情况，如果根本节点不是叶的节点，至少要有两个子节点，这是一个。特殊情况如果根是叶的节点，就是说一开始的时候这个树只有一个节点，就是根有叶，B+树一开始只有一个节点，然后在里头放关键字值，比如说关键字值，如果我的分差数是 n 的话，最多放 n 减一个，当放到n减一个刚放第n的时候，就把翻出两半，左边一个右边一点，然后根节点只有一个文件，就是中间这块拉出来数量，然后左边右边又继续增长以后，当然买了以后又分裂以后，关键之中就越来越多。另外一个就是这样分裂，轮到这一层的分裂码了，放不下了会增加一个新的层，B+树的数据结构的节点下，指针关键字怎么交替主权，所以这里头假定有一到 n减一这么多个关键字也是关键字，节点当中就可以最多可以存存 N减一个，最多存n减一个，还有个上限。这个上限取决于几个因素，第一个节点的空间大小，第二指针的大小和我关键字值的空间大小。因为总的加起来不能超过总的数目，但是这个数据结构是这样一个结构。
这样一个节点当中，的一个关键字k我要查找的时候是按顺序排的，需要一个顺序就是k1小于k2，k2小于k3，严格单调的。可以按隔断查找和顺序查找，比跟k1比≤k一，到p1这个指标往下一层，如果比k1大又比p2小，小于等于p2，就在这个指标其他以此类推，就是的长的过程，因为有序的其实实际在这个节点当中也可以用隔断查找，很快定位到有两个指针输这节点能向哪个分叉。再点，ki方就是搜索的关键资质，Pi就是子节点的指针，到非叶节点上或者记录桶指针。如果在业务节点当中这里存放的是到相应的记录的指的或者是记录的指针桶啊，就有几种情况。每个月的节点的搜索键是有序的，就是k1小于k2，k2小于k3，一直到kn-1;利用这个特征可以进行整改调整，叶节点是 i1跑到n-1，指针 pi要么是指向具有相应搜索键值的文件记录，或者指向具有搜索键值的所有文件记录的一个指针桶，这有两种。另外就是搜索键不构成主件或者不是唯一键的时候，还需要桶结构，是一个关键字值的记录可能多的，这个时候应该是指向一个指针桶，指针桶里头再包含有相应的指针到进入指针，这个是的一个例子。
另外如果L1，L2是两个键值点，并且 i 小于 j,l 的所有电值也小于lf键，实际上大家做 B+树的叶子节点，把串起来就是一个链表，实际上就是一个稠密索引的链表，就是这个节点做一个稠密索引的一个链表，指向关键词顺序的下一节点，这样的话可以做成一个列表。pn的时候就不再需要，因为第一个指针对于第一个关键点到叶节点，最后多出来指针就指向这个下一个节点，是我的节点后续节点，形成了一个现金代表。非叶节点对叶节点实际上是一个多级稀疏索引，具有m的指针的非叶节点，m应该≤n，如果是非根节点的话就是＜n然后＞n/2啊，在n/2和n之间这个值。pn呢就指向指数，所有搜索键值小于k，非叶节点当中，每一个只算了下一级的，也可能列减，有可能下一节可以，但是最上面有一个根节点，在根节点结构当中有可能只有一个环节，除了根节点以外，其他都一定要过半，这是的结构上的要求。这是 B+树的一个例子。
这是针对分行名称建的一个B+树。会发现B+树有一个特点，就是在叶子的节点当中是把所有关键字值都出现了，然后非有一点是个吸收作用，所以在这一层上是把当中的某一些值被锁定掉，到上面就更吸收，到后面就起诉了，只有一个值，这是B+树。假定 n=3，就是说每一个节点当中可以有三个分叉，最多只能有两个关键组织，的只能放两个。
这是这是另外一个例子，如果n等于5的话叶结点有2~4个，也就是说因为5对（5-1）/2除在调整是2到n减1就是4呃，n=5就这么多个值。
根以外的非叶节点必须有3~5个子节点，因为大家知道子节点的数目是的节点当中关键字数目加一，因为每个关键字左边一个右边一个，连起来的话正好比他数多100，所以就2~4就是3~5，根节点至少有两个字节点，这是的结构。
一些观察，关于B+树的。对B+树的查找过程，从根节点开始，在根节点的关键字值比较后找到的分支分叉后头到下一层再去找，采访过程一定是从根节点沿着某条路径就会到叶节点，查找过程一定是这样的过程，这是关于算算法的细节，我就不详细讲了，复杂度分析，也不详细讲，复杂度大概是【log[n/2](K)】如果有k的搜索键值，我这里的所有的键值个数是 k 的，这里头节点一般的大小在 B+树实现的时候，一般节点大小一般就跟磁盘的扩大量一样，就是一个磁盘块成一个节点，知道一个磁盘块空间是4:96个字节，有4k字节， n 一般取值的100，k 有100个分差，假定每个索引下占40个字节，这个时候大概1个节点可以有100个分段，假定现在要搜索的关键词只有100张搜索键值，n等于100，一次挖到最终只要4个节点。因为100倍，除以2是50，50个对100万求log值，log 下来的就是4，效率是很高的，只要访问4个节点就可以找到，如果没有索引的话，意味着要搜索100万的页读进来，把过一遍扫一遍，这个性能提高很高的。如果二叉树的话大概多少是20个，差别还是很大的，所以B+树比二叉树效率更高。但是大家注意这个是在外存到内存这一块，设备如果在内存里头这两个没有区别，如果存储没有这个区别的话，是没有区别的， 因为快设备底数的设计当中，其实利用了磁盘的块设备份，所以的每个节点都是一个物理块为单位。如果都在内存里头的，B+树和二叉树的效率没有区别，因为数学算出去了，只不过是取得指数的底数不一样，但是总的数目是不会变的，但是因为是快速的，所以用 B+树比二叉树效率要高。
B+树更新插入插入的操作过程，主要就是一个节点分裂过程，这里讲了一大堆，不直观，补充的内容关于B+树的操作。前面的内容跳过，主索引辅助索引，这里头有些跟书上内容不完全一样，对在索引当中有一个很重要的这里头要给大家讲一下。
倒排索引。刚才看到作业主要是针对关于表的，针对记录的，而这个是针对文本文件，文本文件我是可以可以见，所以叫什么叫倒排索引。因为文本文件存的时候，当然可以按照字符流按字符把存在里头可以带有个人的信息，比如我的 word 文档或者就是 text 的文本，搜索的时候一般是用关键词，把这个词拿来以后到这里去匹配，找到有这个词的那些文本或者段落，这就是文本查找。文本查找用关键词进行搜索的时候，可以想如果文本量很慢，如果在文本上这么去匹配的，性能是非常差，一些优化的算匹配的研究数据结构理论学应该都学过，对于这样的东西也可以检索点，索引叫倒排索引。就是把关键词抽出来，然后对于每个关键词，我可以索引出他所在的文档当中出现次数以及出现位置，这个就是倒排索引，比如说我这样写这个单词，健康这个单词 IBM 一个或者是超级计算机 computer，Watson比如说这个单词，这个单词他在文档一里头出现了一次是在第十一行有这个出现在第十五行、第八十一行、第二2百二行202，这个意思表示出现在这个文档当中，出现在哪几个行，这个数字代表出现在第几行，这个时候之所以就叫倒排行为。倒排索引，因为找的时候印了一个倒排索引表，查找的关键词说先到这个关键词表里找，PK上如果我要查收入卡多了，卡内存我一查打到了，知道在文档1出现在第二行第十二行开发，做索引键的时候大家做其实也有相应算法，倒排索引的话，可以去把文本扫一步，关键词对关键词见有相应的算法见倒排作用，为什么就造成是由词到文档正排，哪个文档里包含什么词，查哪个文档都包含哪些词。进一步处理的话就可以做自然语言处理一些东西，以后就自然语言处理的话这个词，然后再用盈余与分析或营运空间，在建可以建立什么聚类，聚完类似的话题分析话题聚类就可以做很多这方面，也跟自然语言处理有些关系，就不是的内容给提一下，这个叫倒排索引。
实际上上网的时候，搜索引擎本质上讲是一个网页倒排索引，用谷歌百度的话，本质上讲就是一个倒排索引，只不过倒排索引又解决另外一个问题，因为这是大数据问题，因为我不知道网页这个量非常大，把爬虫拿过来以后，网页里头内容一也是一堆文本，这一堆的文本也要建这种索引，索引还有个排序问题，因为可以发现一个词的涉及到这个词的网页成千上万，就要分析哪一个网页跟关系更大，那就大数据算法就会讲一下怎么来排序，又转化为一个图的问题，实际上是一个，因为网页和网页之间他们会有超链以后就变成了一个图，最后就变成一个链接数多少，我排序的时候这个词在出现过，指向我的重要程度怎么来分类，怎么来排？有一套算法，算法实际上就变成一个图算法，这不就是一个图的计算问题，只不过这个图非常大，图大的无边无际了，后面讲大数据，讲讲这个问题，这个是另外一个问题。就倒排索引。正排索引也就是说从文档到词汇，这个叫正排，倒排就是从词到文档倒过来。
这个东西在数据库里头和原来这个路数不太一样，就这个倒排索引是针对关键词的，还可以建立更高效的叫语义索引，这就是利用语义了词的考虑词的语义，也可以考虑到第二章讲的第二章数据模型当中，本体，语义数据模型，利用词的同义词、近义词、反义词利用这些还有词和词之间的这些关系，概念之间的语义关系可以算余距离，完成的走有些就用到AI的算法，因为可以用机器学习，有大量的语料去训练去学。找文档的时候可以帮助我快速定位到要的文档，这是倒排索引。
其他索引这里还提到多级索引，多属性索引、散列索引、网格索引，后面会讲到，一般在空间数据库里头就可以用到网络索引。大家知道这个时候在空间数据库上，在电子地图当中有很多空间查找，比方要查找一个位置，查到在哪，或者查找某一个区域里头，比如现在想要吃饭了，可能就在手机打开高德地图或者百度地图，上面点着美食，就会在附近区域里头的所有的餐馆就会给标出，这个实际上是一个空间的一种查询。B+树实际上就是多级索引的一种特殊类型多级索引，每一个索引的节点大小是固定的，就固定大小的，另外是平衡的，然后要过半就满足那几个要求的，叫多级索引，B+树就是说以树型数据结构组织多级索引。
B+树的操作，怎么来保证所指针的利用率都在百分之过半，能保证这里头有一系列的数据结构和算法的设计，前面说过就是有一系列方法，一个块就能放多少索引项由这几个因素，每个索引项有一个关键字值再加一个指标，这两个大小啊那再加后面的一个指标，就是n减一个，索引项再加多一个指针，他们办的空间大小是可以算出来，比如说我存储罐大小是4096自己，我用整形的所有字段值是4个字节，指针假定1个指针，这8个字节是持久指针，这个 n 应该满足4乘n-1+8n小于等于4096，不等式方程稍微一解n个最大值就是不能超过341。示例存储块=4096 Byte
整数型索引字段值=4 Byte 指针=8 Byte
则: n 应满足4(n-1)+8n<=4096
n 取最大值
n=341
就说一个可以最多有340个分叉，当指标做的大的话，n就越这个值就越小。
插入操作的过程看个例子，假定这里头有三个关键字值14 52 78，一定是从小到大排的，有4个指针，指针指向小于14的，大于等于14小于52，和大于等于52小于78。等号到底是在哪边？这是个边界值。习惯上来说可以放在这边，也可以在另一边，这是一个边界条件的事情。奇怪的就按照这个，也有的书上他把这个地方变成一个等号，这边就变成了＞、≤，比如非叶节点 n=三，这个是另外一个节点的例子。保证过半，实际当中包含的关键字时一定要满足这个条件，n/2≤d≤n，满足非叶节点至少一半以上的空间是可以利用上的。
另外一个例子，这个特点就是所有工作值在叶的节点，非叶节点会重复出现的，在叶节点形成一个有序列的，把所有的关键字值是放这。
2 3 5 7 11 13 17 19 23 29，这里头最多也有三个，这里面没有写就是说他没填满，可以空一个，但是所有的当中至少要有两个以上，有三个不能少于两个，但这个只有一个，所以这个结构当中是有问题，实际上23应该放在这边，这个结构化有点不对。现在就画成这样，目前看这就是一个n=3的一个B+树，有三层的一个B+树，有两个非叶节点，非根非叶节点，一个根节点根节点总是一个，上面是叫非叶节点的，底下是叶节点，也就是叶节点的块的集合就是主文件完整的索引，即:最低一级。构成主文件完整的稠密索引。上面是新索引，7 23 31 43，本身的索引数是15个，这是个稀疏的。
如何保证平衡？插入删除记录时，伴随节点做相应分裂与合并；分裂与合并将调整部分结点块中索引项。插入的时候可能导致分裂，删除的时候可能导致合并。看这个例子，假定能够另外还有什么自动保持与主文件大小相适应的数字层次，每个索引块的指针利用率要在50%过半，要保证这两点。
建立稠密索引、插入删除操作合并操作算法在一般的在教科书里头实际上都有完整的算法，就是B+树的查询的算法，B+树的插入记录的算法，逻辑挺复杂的，都写了一大堆，B+树的删除记录的算法，在教材里都有。主要看一下怎么对进行检索，怎么进行增删改操作，怎么来完成节点的分裂，怎么来进行分裂和合并。
下面看就节点的插入和节点分裂的过程，B+树要插入一个值为40的记录，首先要定位，定位的记录要往里放，比较40跟13比，大于13，就要往一边走，小于13往另一边走，到这么比23大比31，大比43小，所以沿着这条走到这来就31 37 41就40了，应该插入到一个节点，但这个节点呢已经满了，相当于这已经有三块钱资质，要增加一个，就相当于我这个房间里有三个床位，现在又要来一个新的人，住不下了就要分裂，就把这个房子要把他们4个关键指标分成2个节点，这个叫分裂，就要把这个节点拆成两个节点，一边挂两个，这一拆以后带来什么问题了？
这个节点的关键词只要在上一层有反应，要给上一层又要增加一个关键词，下层的又分裂下一层的分裂以后就导致更往上层的过程就走不过的。看这个过程，传染过程的进程当中，首先查找关键字值记录的业绩节点，然后应查处节点由于一码就要申请一个协议，要分裂同时调整。
