算法题之翻页查找

   当你浏览百度很多产品的网页时，你会发现有很多翻页查找功能。现在有一组有序网页数据，要支持查询、删除、追加到末尾三种操作。其中查找就是查询某一页的数据。例如，每页显示20个，现在要查第50页，假如这些有序数据用一个数组来保存，则从下标20*49开始，直接返回后面的20即可，但是，当删除时，会有大量的数据移动，所以就对删除操作效率较低。另一种策略是不直接删除，只在数组作一个标记，表示那个位置之不理的数据已删除，这样可以避免移动数据，但是，翻页查询时必须从头开始计数，数一下应该从那个位置开始返回，所以这个策略对查询的效率不高。

限制：假如（1）这些操作都是在硬盘上（2）网页的大小都是不相同的（3）页面的总数不超过10M（4）单页面不超过100K，这样的限制下，请问如何设计你的数据结构，使得查询、删除、追加到末尾操作都比较高效呢？
要求：设计思路，数据结构的实现及操作的描述。

   这题刚看到第一反映是B+ tree,细细想想情景都错了,B+ Tree一般是内存不够用的时候才用的,B+的删除这里也不太一样。tree其实都不大好实现了,因为在逻辑上是连续的。

   A[i][20];

 

   删除:

     WEB W[50];//W[0]=1第一页的起始指针A[0][0],W[i]=i+1第i+1页的起始指针A[i][0]

   删除的时候将W[i]=0,W[j>i]=W[j]-1;

     既然移动指针的操作效率不可接受,内存又够用,那就尽量时间换空间,只是将对应位置置0,以后的

   位-1.如查找第30页的时候,还是先看看W[29]=?,W[29]肯定是<=30的,如果小于30再W[30]...只要删除操作不是太多这样是完全ok的. 

 

 

   添加:

     直接扩大W数组

 

   查找:第x页

     先在W数组中找到了W[i]=页再去A[i][0..20]输出页。

 

   写到这里的时候突然想到这是不是就是所谓的index,额外的空间换取一定的index方便查找...

    因为这里完全是数字,而不是字符串Index,如果是字符串的话,就是我们常见的数据库实现的btree  hash这些做index了.

 

 

   一家之言,不妥之处还望各位海涵!!!也欢迎讨论^_^.学习这东西就是这样你会A,我会B谈论下我们就会A+B了.

 

   如果删除过于频繁的话还是建议用链表，额外的记录每页的起始指针的数组还是有!!!!

   typedef struct list

    {

      ..... 

      struct list* next;

    }LIST;

    LIST L_ARRAY[50];