B-Tree就是我们常说的B树,一定不要读成B减树,否则就很丢人了。B树这种数据结构常常用于实现数据库索引,因为它的查找效率比较高。

SQLite在存储在外部的数据库是以B-Tree来组织的。关于B-tree的细节,参考
**
** Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
** “Sorting And Searching”, pages 473-480. Addison-Wesley
** Publishing Company, Reading, Massachusetts.
**

B树

Hash索引与B-Tree索引,hash索引b-tree

本文简单介绍了在PG数据库B-Tree索引的物理存储结构中Special
space部分,包括根节点、左右兄弟节点等相关索引结构信息,以及初步探讨了PG在物理存储上如何保证索引的有序性。

磁盘IO与预读

磁盘读取依靠的是机械运动,分为寻道时间、旋转延迟、传输时间三个部分,这三个部分耗时相加就是一次磁盘IO的时间,大概9ms左右。这个成本是访问内存的十万倍左右;正是由于磁盘IO是非常昂贵的操作,所以计算机操作系统对此做了优化:预读;每一次IO时,不仅仅把当前磁盘地址的数据加载到内存,同时也把相邻数据也加载到内存缓冲区中。因为局部预读原理说明:当访问一个地址数据的时候,与其相邻的数据很快也会被访问到。每次磁盘IO读取的数据我们称之为一页(page)。一页的大小与操作系统有关,一般为4k或者8k。这也就意味着读取一页内数据的时候,实际上发生了一次磁盘IO。

基本思想是文件包含的每一页都包括N个数据库入口和N+1个指向子页的指针。文件分成很多页存储。为什么这么干,因为内存分页管理机制闹得。外存中每个页就是B树的一个节点。

**       即二叉搜索树:

Hash索引                                                                              

      Hash
索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree
索引需要从根节点到枝节点,最后才能访问到页节点这样多次的IO访问,所以
Hash 索引的查询效率要远高于 B-Tree 索引。
      可能很多人又有疑问了,既然 Hash 索引的效率要比 B-Tree
高很多,为什么大家不都用 Hash 索引而还要使用 B-Tree
索引呢?任何事物都是有两面性的,Hash 索引也一样,虽然 Hash
索引效率高,但是 Hash
索引本身由于其特殊性也带来了很多限制和弊端,主要有以下这些。

(1)Hash 索引仅仅能满足"=","IN"和"<=>"查询,不能使用范围查询。
     由于 Hash 索引比较的是进行 Hash 运算之后的 Hash 值,所以它只能用于等值的过滤,不能用于基于范围的过滤,因为经过相应的 Hash 算法处理之后的 Hash 值的大小关系,并不能保证和Hash运算前完全一样。
(2)Hash 索引无法被用来避免数据的排序操作。
     由于 Hash 索引中存放的是经过 Hash 计算之后的 Hash 值,而且Hash值的大小关系并不一定和 Hash 运算前的键值完全一样,所以数据库无法利用索引的数据来避免任何排序运算;
(3)Hash 索引不能利用部分索引键查询。
     对于组合索引,Hash 索引在计算 Hash 值的时候是组合索引键合并后再一起计算 Hash 值,而不是单独计算 Hash 值,所以通过组合索引的前面一个或几个索引键进行查询的时候,Hash 索引也无法被利用。
(4)Hash 索引在任何时候都不能避免表扫描。
     前面已经知道,Hash 索引是将索引键通过 Hash 运算之后,将 Hash运算结果的 Hash 值和所对应的行指针信息存放于一个 Hash 表中,由于不同索引键存在相同 Hash 值,所以即使取满足某个 Hash 键值的数据的记录条数,也无法从 Hash 索引中直接完成查询,还是要通过访问表中的实际数据进行相应的比较,并得到相应的结果。
(5)Hash 索引遇到大量Hash值相等的情况后性能并不一定就会比B-Tree索引高。
     对于选择性比较低的索引键,如果创建 Hash 索引,那么将会存在大量记录指针信息存于同一个 Hash 值相关联。这样要定位某一条记录时就会非常麻烦,会浪费多次表数据的访问,而造成整体性能低下。

一、测试数据

测试数据同上一节,索引文件raw data:

[xdb@localhost utf8db]$ hexdump -C base/16477/2663700000000 01 00 00 00 20 5d 0e db 00 00 00 00 40 00 f0 1f |.... ]......@...|00000010 f0 1f 04 20 00 00 00 00 62 31 05 00 03 00 00 00 |... ....b1......|00000020 01 00 00 00 00 00 00 00 01 00 00 00 00 00 00 00 |................|00000030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 f0 bf |................|00000040 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*00001ff0 00 00 00 00 00 00 00 00 00 00 00 00 08 00 00 00 |................|00002000 01 00 00 00 98 5c 0e db 00 00 00 00 28 00 b0 1f |.....\......(...|00002010 f0 1f 04 20 00 00 00 00 e0 9f 20 00 d0 9f 20 00 |... ...... ... .|00002020 c0 9f 20 00 b0 9f 20 00 b0 9f 20 00 00 00 00 00 |.. ... ... .....|00002030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*00003fb0 00 00 00 00 04 00 10 00 10 00 00 00 00 00 00 00 |................|00003fc0 00 00 00 00 03 00 10 00 08 00 00 00 00 00 00 00 |................|00003fd0 00 00 00 00 02 00 10 00 04 00 00 00 00 00 00 00 |................|00003fe0 00 00 00 00 01 00 10 00 02 00 00 00 00 00 00 00 |................|00003ff0 00 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 |................|00004000

B-Tree与二叉查找树的对比

  我们知道二叉查找树查询的时间复杂度是O(logN),查找速度最快和比较次数最少,既然性能已经如此优秀,但为什么实现索引是使用B-Tree而不是二叉查找树,关键因素是磁盘IO的次数。

数据库索引是存储在磁盘上,当表中的数据量比较大时,索引的大小也跟着增长,达到几个G甚至更多。当我们利用索引进行查询的时候,不可能把索引全部加载到内存中,只能逐一加载每个磁盘页,这里的磁盘页就对应索引树的节点。

| Ptr(0) | Key(0) | Ptr(1) | Key(1) | … | Key(N-1) | Ptr(N) |

Ptr(0)指向的页上的所有的key的值都小于Key(0)。所有Ptr(1)指向的页和子页的所有的key的值都大于Key(0),小于Key(1)。所有Ptr(N)指向的页和子页的key的值都大于Key(N-1),等等。

为了知道一个特定的key,需要从磁盘上以O(long(M))来读取,其中M是树的阶数。内存中找不到了,就发生缺页中断。
主要是解决内存中找不到的问题。一方面换出来一些。一方面换进去一些。换进去的时候要找到他们再硬盘的哪个页面上啊。
(B树的优点就是适合于用块儿存储的存储设备上。)利用所以,可以知道他们们在哪个页面上。

在SQLite的实现中,一个文件可以含有1个或的过独立的BTree。每一个BTree由它的根页的索引来标识。所有入口的key和数据组成了有效负荷(payload)。数据库的一页有一个固定的有效负荷总量。如果负荷大于了预先设定的值,那么剩余的字节就会被存储在溢出页上。一个入口的有效负荷再加上前向指针(the
preceding
pointer)构成了一格(cell)。每一页都有一个小头部,包含了Ptr(N)指针和其它一些信息,例如key和数据的大小。

格式细节
一个文件分成了多个页。第一页叫做页1,第二页叫做页2,一次类推。页的个数为0表示没有页。页的大小可以从512

65536。每一页或者是一个btree页,或者是一个freelist页,或者是一个溢出页。
第一页一定是一个btree页。第一页的前面100个字节包含了一个特殊的首部(文件头),它是这个文件的描述。
文件头的个数如下:
** OFFSET SIZE DESCRIPTION
** 0 16 Header string(首部字符串): “SQLite format 3\000”
** 16 2 Page size in bytes(页的字节数).
** 18 1 File format write version(文件写操作的版本)
** 19 1 File format read version (文件读操作的版本)
** 20 1 Bytes of unused space at the end of each
page(每一页结尾未使用的字节)
** 21 1 Max embedded payload fraction(最大的嵌入有效负荷分片)
** 22 1 Min embedded payload fraction(最小的嵌入有效负荷分片)
** 23 1 Min leaf payload fraction(最小的页有效负荷分片)
** 24 4 File change counter (文件变化计数器)
** 28 4 Reserved for future use (保留字节)
** 32 4 First freelist page (第一个freelist页)
** 36 4 Number of freelist pages in the file
(本文件中freelist页的个数)
** 40 60 15 4-byte meta values passed to higher layers()
**
所有的整数都是大端的。

每次修改文件时,文件变化计数器都会增加。这个计数器可以让其他进程知道何时文件被修改了,他们的cache是否需要清理。

最大嵌入有效负荷分片是一页的所有可用空间,被标准B-tree(非叶数据)表的单独的一个所能使用的总量。值255代表100%。默认情况下,一格(cell)的最大量被限制为,至少有4格才能填满一页。因此,默认的最大嵌入负荷分片是64。

如果一页的有效负荷大于了最大有效负荷,那么剩下的数据就要被存储到溢出页。一旦分配了一个溢出页,有可能会有许多数据也被转移到这个溢出页,但是不会让格cell的大小小于最小嵌入有效负荷分片的。

最小页有效负荷分片与最小嵌入有效负荷分片类似,但是它是应用于LEAFDATA
tree中的叶节点。一个LEAFDATA的最大有效负荷分片为100%(或者是值255),它不用再首部指定。

BTree的每一页被分为三部分:首部,格(cell)指针数组,和格cell的内容。页1还会在页首部有100字节的文件头。
**
** |—————-|
** | file header | 100 bytes. Page 1 only.
** |—————-|
** | page header | 8 bytes for leaves. 12 bytes for interior nodes
** |—————-|
** | cell pointer | | 2 bytes per cell. Sorted order.
** | array | | Grows downward
** | | v
** |—————-|
** | unallocated |
** | space |
** |—————-| ^ Grows upwards
** | cell content | | Arbitrary order interspersed with freeblocks.
** | area | | and free space fragments.
** |—————-|
**
页首部如下图所示:
**
** OFFSET SIZE DESCRIPTION
** 0 1 Flags. 1: intkey, 2: zerodata, 4: leafdata, 8: leaf
** 1 2 byte offset to the first freeblock
** 3 2 number of cells on this page
** 5 2 first byte of the cell content area
** 7 1 number of fragmented free bytes
** 8 4 Right child (the Ptr(N) value). Omitted on leaves.
**
标志位定义了这个BTree页的格式。叶leaf标志意味着这一页没有孩子children。zerodata0数据表示这一页只含有key,没有数据;intkey标志意味着key是一个整数,而且是被存储在格cell首部的key大小处,而不是在有效负荷区域。

格cell指针数组从页首部开始。格cell指针数组包含0个或多余2个字节的数字,这个数字代表格cell内容区域中的格cell内容从文件起始位置的偏移量。格cell指针式有序的。系统尽力保证空闲空间位于最后一个格cell指针之后,这样可以保证新的格cell可以很快的添加,而不用重新整理(defragment)这一页。

格cell内容存储在页的末尾,且是向文件的起始方向增长。

在格cell内容区域中的未使用的空间被收集到链表freeblocks上。每一个freeblock至少有4个字节。第一个freeblock的偏移在页首部给出了。Freeblock是增序的。因为一个freeblock至少有4个字节,所有在格cell内容区域的3个或是哦啊与3个的未用空间不能存在于freeblock链表上。这些3个或少于3个的空闲空间被称为碎片。所有碎片的总个数被记录下来,存储于页首部的偏移7的位置。

** SIZE DESCRIPTION
** 2 Byte offset of the next freeblock
** 2 Bytes in this freeblock
**

格cell是可变长度的。格cell被存储于页的末尾格cell内容区域。指向格cell的cell指针数组紧跟在页首部的后面。格cell不必是连续或者有序的,但是格cell指针是连续和有序的。

格cell内容充分利用了可变长度整数。可变长度整数是从1到9个字节,每个字节的低7位被使用。整个整数由8位的字节组成,其中第一个字节的第8位被清零。整数最重要的字节出现在第一个。可变长度整数一般不多于9个字节。作为一种特殊情况,第九个字节的所有8个字节都会被认为是数据。这就允许了64位整数变编码为9个字节。
** 0x00 becomes 0x00000000
** 0x7f becomes 0x0000007f
** 0x81 0x00 becomes 0x00000080
** 0x82 0x00 becomes 0x00000100
** 0x80 0x7f becomes 0x0000007f
** 0x8a 0x91 0xd1 0xac 0x78 becomes 0x12345678
** 0x81 0x81 0x81 0x81 0x01 becomes 0x10204081
本篇文章来源于 Linux公社网站(www.linuxidc.com)
原文链接:

       1.所有非叶子结点至多拥有两个儿子(Left和Right);

B-Tree索引                                                                           

B-Tree 索引是 MySQL 数据库中使用最为频繁的索引类型,除了 Archive
存储引擎之外的其他所有的存储引擎都支持 B-Tree 索引。不仅仅在 MySQL
中是如此,实际上在其他的很多数据库管理系统中B-Tree
索引也同样是作为最主要的索引类型,这主要是因为 B-Tree
索引的存储结构在数据库的数据检索中有非常优异的表现。
一般来说, MySQL 中的 B-Tree 索引的物理文件大多都是以 Balance Tree
的结构来存储的,也就是所有实际需要的数据都存放于 Tree 的 Leaf Node
,而且到任何一个 Leaf Node
的最短路径的长度都是完全相同的,所以我们大家都称之为 B-Tree
索引当然,可能各种数据库(或 MySQL 的各种存储引擎)在存放自己的 B-Tree
索引的时候会对存储结构稍作改造。如 Innodb 存储引擎的 B-Tree
索引实际使用的存储结构实际上是 B+Tree ,也就是在 B-Tree
数据结构的基础上做了很小的改造,在每一个Leaf Node
上面出了存放索引键的相关信息之外,还存储了指向与该 Leaf Node
相邻的后一个 LeafNode 的指针信息,这主要是为了加快检索多个相邻 Leaf Node
的效率考虑。
在 Innodb 存储引擎中,存在两种不同形式的索引,一种是 Cluster
形式的主键索引( Primary Key ),另外一种则是和其他存储引擎(如 MyISAM
存储引擎)存放形式基本相同的普通 B-Tree 索引,这种索引在 Innodb
存储引擎中被称为 Secondary Index
。下面我们通过图示来针对这两种索引的存放形式做一个比较。

我是天王盖地虎的分割线                                                             

 

 

参考:

二、索引结构信息

索引物理存储结构在上一节已大体介绍,这里主要介绍索引的结构信息。通过pageinspect插件的bt_page_stats函数可以获得索引结构信息,包括root/leaf
page,next & previous page:

testdb=# select * from bt_page_stats('pk_t_index',1); blkno | type | live_items | dead_items | avg_item_size | page_size | free_size | btpo_prev | btpo_next | btpo | btpo_flags -------+------+------------+------------+---------------+-----------+-----------+-----------+-----------+------+------------ 1 | l | 4 | 0 | 16 | 8192 | 8068 | 0 | 0 | 0 | 3

相关的数据结构如下:

//---------------------- src/include/access/nbtree.h/* * BTPageOpaqueData -- At the end of every page, we store a pointer * to both siblings in the tree. This is used to do forward/backward * index scans. The next-page link is also critical for recovery when * a search has navigated to the wrong page due to concurrent page splits * or deletions; see src/backend/access/nbtree/README for more info. * * In addition, we store the page's btree level (counting upwards from * zero at a leaf page) as well as some flag bits indicating the page type * and status. If the page is deleted, we replace the level with the * next-transaction-ID value indicating when it is safe to reclaim the page. * * We also store a "vacuum cycle ID". When a page is split while VACUUM is * processing the index, a nonzero value associated with the VACUUM run is * stored into both halves of the split page. (If VACUUM is not running, * both pages receive zero cycleids.) This allows VACUUM to detect whether * a page was split since it started, with a small probability of false match * if the page was last split some exact multiple of MAX_BT_CYCLE_ID VACUUMs * ago. Also, during a split, the BTP_SPLIT_END flag is cleared in the left *  page, and set in the right page, but only if the next page * to its right has a different cycleid. * * NOTE: the BTP_LEAF flag bit is redundant since level==0 could be tested * instead. */typedef struct BTPageOpaqueData{ BlockNumber btpo_prev; /* left sibling, or P_NONE if leftmost */ BlockNumber btpo_next; /* right sibling, or P_NONE if rightmost */ union { uint32 level; /* tree level --- zero for leaf pages */ TransactionId xact; /* next transaction ID, if deleted */ } btpo; uint16 btpo_flags; /* flag bits, see below */ BTCycleId btpo_cycleid; /* vacuum cycle ID of latest split */} BTPageOpaqueData;typedef BTPageOpaqueData *BTPageOpaque;/* Bits defined in btpo_flags */#define BTP_LEAF (1 << 0) /* leaf page, i.e. not internal page */#define BTP_ROOT (1 << 1) /* root page (has no parent) */#define BTP_DELETED (1 << 2) /* page has been deleted from tree */#define BTP_META (1 << 3) /* meta-page */#define BTP_HALF_DEAD (1 << 4) /* empty, but still in tree */#define BTP_SPLIT_END (1 << 5) /* rightmost page of split group */#define BTP_HAS_GARBAGE (1 << 6) /* page has LP_DEAD tuples */#define BTP_INCOMPLETE_SPLIT (1 << 7) /* right sibling's downlink is missing */

查询结果中,type=l,表示这个block是leaf
block,在这个block中有4个item(live_items=4),没有废弃的items(dead_items=0),没有left
sibling(btpo_prev =0)也没有right sibling(btpo_next
=0),也就是左右两边都没有同级节点。btpo是一个union,值为0,表示该page为叶子page,btpo_flags值为3即BTP_LEAF
|
BTP_ROOT,既是叶子page也是根page。这些信息物理存储在先前介绍过的PageHeader中的special
space中,共占用16个字节:

testdb=# select * from page_header(get_raw_page('pk_t_index',1)); lsn | checksum | flags | lower | upper | special | pagesize | version | prune_xid ------------+----------+-------+-------+-------+---------+----------+---------+----------- 1/DB0E5C98 | 0 | 0 | 40 | 8112 | 8176 | 8192 | 4 | 0testdb=# select 8192+8176; ?column? ---------- 16368[xdb@localhost utf8db]$ hexdump -C base/16477/26637 -s 16368 -n 1600003ff0 00 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 |................|00004000

一、 二叉树

我们先来看二叉树查找时磁盘IO的次:定义一个树高为4的二叉树,查找值为10:

                                         
               
  图片 1

 

第一次磁盘IO:

                       
 图片 2

 

 

 第二次磁盘IO

                         
 图片 3

 

第三次磁盘IO:

                           
 图片 4

 

第四次磁盘IO:

                                 
 图片 5

从二叉树的查找过程了来看,树的高度和磁盘IO的次数都是4,所以最坏的情况下磁盘IO的次数由树的高度来决定。

从前面分析情况来看,减少磁盘IO的次数就必须要压缩树的高度,让瘦高的树尽量变成矮胖的树,所以B-Tree就在这样伟大的时代背景下诞生了。

您可能感兴趣的文章:

  • Android开发之SQLite的使用方法
  • SQLite 中文指南之FAQ
  • sqlite中文乱码问题原因分析及解决
  • SQLite3中的日期时间函数使用小结
  • sqlite3
    top的查询及limit语法介绍
  • SQLite优化方法
  • Sqlite 常用函数 推荐
  • SQLite 错误码整理
  • sQlite常用语句以及sQlite
    developer的使用与注册

       2.所有结点存储一个关键字;

如果对磁盘上的1000W条记录构建索引,最适合用哪种数据结构? A hash table B:AVL-Tree C:B-tree D:list

是A呢还是C呢?
 

三、索引有序性

我们都知道,B-Tree索引是有序的,下面我们看看在物理存储结构上如何保证有序性。插入数据,id=18

testdb=# select * from page_header(get_raw_page('pk_t_index',1)); lsn | checksum | flags | lower | upper | special | pagesize | version | prune_xid ------------+----------+-------+-------+-------+---------+----------+---------+----------- 1/DB0E5C98 | 0 | 0 | 40 | 8112 | 8176 | 8192 | 4 | 0testdb=# -- 插入数据,id=18testdb=# insert into t_index values(18,'4','d');INSERT 0 1testdb=# select * from page_header(get_raw_page('pk_t_index',1)); lsn | checksum | flags | lower | upper | special | pagesize | version | prune_xid ------------+----------+-------+-------+-------+---------+----------+---------+----------- 1/DB0E6498 | 0 | 0 | 44 | 8096 | 8176 | 8192 | 4 | 0-- dump索引页[xdb@localhost utf8db]$ hexdump -C base/16477/26637 -s 819200002000 01 00 00 00 98 64 0e db 00 00 00 00 2c 00 a0 1f |.....d......,...|00002010 f0 1f 04 20 00 00 00 00 e0 9f 20 00 d0 9f 20 00 |... ...... ... .|00002020 c0 9f 20 00 b0 9f 20 00 a0 9f 20 00 00 00 00 00 |.. ... ... .....|00002030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*00003fa0 00 00 00 00 05 00 10 00 12 00 00 00 00 00 00 00 |................|00003fb0 00 00 00 00 04 00 10 00 10 00 00 00 00 00 00 00 |................|00003fc0 00 00 00 00 03 00 10 00 08 00 00 00 00 00 00 00 |................|00003fd0 00 00 00 00 02 00 10 00 04 00 00 00 00 00 00 00 |................|00003fe0 00 00 00 00 01 00 10 00 02 00 00 00 00 00 00 00 |................|00003ff0 00 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 |................|00004000

插入数据,id=17

testdb=# -- 插入数据,id=17testdb=# insert into t_index values(17,'4','d');INSERT 0 1testdb=# checkpoint;CHECKPOINTtestdb=# -- 查看索引数据页头数据testdb=# select * from page_header(get_raw_page('pk_t_index',1)); lsn | checksum | flags | lower | upper | special | pagesize | version | prune_xid ------------+----------+-------+-------+-------+---------+----------+---------+----------- 1/DB0E6808 | 0 | 0 | 48 | 8080 | 8176 | 8192 | 4 | 0-- dump索引页[xdb@localhost utf8db]$ hexdump -C base/16477/26637 -s 819200002000 01 00 00 00 08 68 0e db 00 00 00 00 30 00 90 1f |.....h......0...|00002010 f0 1f 04 20 00 00 00 00 e0 9f 20 00 d0 9f 20 00 |... ...... ... .|00002020 c0 9f 20 00 b0 9f 20 00 90 9f 20 00 a0 9f 20 00 |.. ... ... ... .|00002030 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 |................|*00003f90 00 00 00 00 06 00 10 00 11 00 00 00 00 00 00 00 |................|00003fa0 00 00 00 00 05 00 10 00 12 00 00 00 00 00 00 00 |................|00003fb0 00 00 00 00 04 00 10 00 10 00 00 00 00 00 00 00 |................|00003fc0 00 00 00 00 03 00 10 00 08 00 00 00 00 00 00 00 |................|00003fd0 00 00 00 00 02 00 10 00 04 00 00 00 00 00 00 00 |................|00003fe0 00 00 00 00 01 00 10 00 02 00 00 00 00 00 00 00 |................|00003ff0 00 00 00 00 00 00 00 00 00 00 00 00 03 00 00 00 |................|00004000

索引的数据区,并没有按照大小顺序排序,\x11在\x12的后面,但在索引页的头部ItemId区域是有序的,第5个ItemId(\x00209f90)指向的是17,而第6个ItemId(\x00209fa0)指向的是18,通过索引数据指针的有序保证索引有序性。

二、B-Tree

m阶B-Tree满足以下条件:

1、每个节点最多拥有m个子树

2、根节点至少有2个子树

3、分支节点至少拥有m/2颗子树(除根节点和叶子节点外都是分支节点)

4、所有叶子节点都在同一层、每个节点最多可以有m-1个key,并且以升序排列

 如下有一个3阶的B树,观察查找元素21的过程:

                                         
                                 
  图片 6

第一次磁盘IO:     

                                         
               
 图片 7

第二次磁盘IO:

                                         
     
  图片 8

这里有一次内存比对:分别跟3与12比对

第三次磁盘IO:

                                         
         
 图片 9

这里有一次内存比对,分别跟14与21比对

从查找过程中发现,B树的比对次数和磁盘IO的次数与二叉树相差不了多少,所以这样看来并没有什么优势。

但是仔细一看会发现,比对是在内存中完成中,不涉及到磁盘IO,耗时可以忽略不计。另外B树种一个节点中可以存放很多的key(个数由树阶决定)。

相同数量的key在B树中生成的节点要远远少于二叉树中的节点,相差的节点数量就等同于磁盘IO的次数。这样到达一定数量后,性能的差异就显现出来了。

       3.非叶子结点的左指针指向小于其关键字的子树,右指针指向大于其关键字的子树;

主键索引方式是不是哈希索引

通常不是Hash索引!而是B+树索引。B+树当然没有Hash快,Oracle数据库可以指定索引为Hash索引,叫cluster索引!
 

Hash索引
Hash
索引结构的特殊性,其检索效率非常高,索引的检索可以一次定位,不像B-Tree
索引需要从根…

四、小结

小结一下,知识要点:1、Special Space:介绍了索引PageHeaderData的Special
Space的存储结构,通过Special
Space可以获得B-Tree的root、左右sibling等信息;2、有序性:索引Page通过索引项指针保证有序性。

最后:

Don’t Be Afraid To Explore Beneath The Surface

图片 10Captain
Nemo at the helm

Professor Aronnax risked his life and career to find the elusive
Nautilus and to join Captain Nemo on a long series of amazing
underwater adventures. We should do the same: Don’t be afraid to dive
underwater – inside and underneath the tools, languages and
technologies that you use every day. You may know all about how to use
Postgres, but do you really know how Postgres itself works internally?
Take a look inside; before you know it, you’ll be on an underwater
adventure of your own.Studying the Computer Science at work behind the
scenes of our applications isn’t just a matter of having fun, it’s
part of being a good developer. As software development tools improve
year after year, and as building web sites and mobile apps becomes
easier and easier, we shouldn’t loose sight of the Computer Science we
depend on. We’re all standing on the shoulders of giants – people like
Lehman and Yao, and the open source developers who used their theories
to build Postgres. Don’t take the tools you use everyday for granted –
take a look inside them! You’ll become a wiser developer and you’ll
find insights and knowledge you could never have imagined before.

 三、B树的新增

在刚才的基础上新增元素4,它应该在3与9之间:

                               
 图片 11

                                   
 图片 12

                                   
 图片 13

 

       如:图片 14

四、B树的删除

 删除元素9:

                               
  图片 15

 

                                 
  图片 16

B树的搜索,从根结点开始,如果查询的关键字与结点的关键字相等,那么就命中;否则,如果查询关键字比结点关键字小,就进入左儿子;如果比结点关键字大,就进入右儿子;如果左儿子或右儿子的指针为空,则报告找不到相应的关键字;

五、总结

  插入或者删除元素都会导致节点发生裂变反应,有时候会非常麻烦,但正因为如此才让B树能够始终保持多路平衡,这也是B树自身的一个优势:自平衡;B树主要应用于文件系统以及部分数据库索引,如MongoDB,大部分关系型数据库索引则是使用B+树实现。

 

 

       如果B树的所有非叶子结点的左右子树的结点数目均保持差不多(平衡),那么B树的搜索性能逼近二分查找;但它比连续内存空间的二分查找的优点是,改变B树结构(插入与删除结点)不需要移动大段的内存数据,甚至通常是常数开销;

       如:图片 17

但B树在经过多次插入与删除后,有可能导致不同的结构:

图片 18

 

右边也是一个B树,但它的搜索性能已经是线性的了;同样的关键字集合有可能导致不同的树结构索引;所以,使用B树还要考虑尽可能让B树保持左图的结构,和避免右图的结构,也就是所谓的“平衡”问题;      

      
实际使用的B树都是在原B树的基础上加上平衡算法,即“平衡二叉树”;如何保持B树结点分布均匀的平衡算法是平衡二叉树的关键;平衡算法是一种在B树中插入和删除结点的策略;

 

B-树

       是一种多路搜索树(并不是二叉的):

       1.定义任意非叶子结点最多只有M个儿子;且M>2;

       2.根结点的儿子数为[2, M];

       3.除根结点以外的非叶子结点的儿子数为[M/2, M];

      
4.每个结点存放至少M/2-1(取上整)和至多M-1个关键字;(至少2个关键字)

       5.非叶子结点的关键字个数=指向儿子的指针个数-1;

       6.非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] <
K[i+1];

       7.非叶子结点的指针:P[1], P[2], …,
P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1],
K[i])的子树;

       8.所有叶子结点位于同一层;

       如:(M=3)

图片 19

 

 B-树的搜索,从根结点开始,对结点内的关键字(有序)序列进行二分查找,如果命中则结束,否则进入查询关键字所属范围的儿子结点;重复,直到所对应的儿子指针为空,或已经是叶子结点;

B-树的特性:

       1.关键字集合分布在整颗树中;

       2.任何一个关键字出现且只出现在一个结点中;

       3.搜索有可能在非叶子结点结束;

       4.其搜索性能等价于在关键字全集内做一次二分查找;

       5.自动层次控制;

      
由于限制了除根结点以外的非叶子结点,至少含有M/2个儿子,确保了结点的至少利用率,其最底搜索性能为:

图片 20

 

其中,M为设定的非叶子结点最多子树个数,N为关键字总数;

      
所以B-树的性能总是等价于二分查找(与M值无关),也就没有B树平衡的问题;

      
由于M/2的限制,在插入结点时,如果结点已满,需要将结点分裂为两个各占M/2的结点;删除结点时,需将两个不足M/2的兄弟结点合并;

 

B+树

       B+树是B-树的变体,也是一种多路搜索树:

       1.其定义基本与B-树同,除了:

       2.非叶子结点的子树指针与关键字个数相同;

       3.非叶子结点的子树指针P[i],指向关键字值属于[K[i],
K[i+1])的子树(B-树是开区间);

       5.为所有叶子结点增加一个链指针;

       6.所有关键字都在叶子结点出现;

       如:(M=3)

图片 21

 

B+的搜索与B-树也基本相同,区别是B+树只有达到叶子结点才命中(B-树可以在非叶子结点命中),其性能也等价于在关键字全集做一次二分查找;

       B+的特性:

      
1.所有关键字都出现在叶子结点的链表中(稠密索引),且链表中的关键字恰好是有序的;

       2.不可能在非叶子结点命中;

      
3.非叶子结点相当于是叶子结点的索引(稀疏索引),叶子结点相当于是存储(关键字)数据的数据层;

       4.更适合文件索引系统;

 

B*树

       是B+树的变体,在B+树的非根和非叶子结点再增加指向兄弟的指针;

图片 22

 

B*树定义了非叶子结点关键字个数至少为(2/3)*M,即块的最低使用率为2/3(代替B+树的1/2);

      
B+树的分裂:当一个结点满时,分配一个新的结点,并将原结点中1/2的数据复制到新结点,最后在父结点中增加新结点的指针;B+树的分裂只影响原结点和父结点,而不会影响兄弟结点,所以它不需要指向兄弟的指针;

      
B*树的分裂:当一个结点满时,如果它的下一个兄弟结点未满,那么将一部分数据移到兄弟结点中,再在原结点插入关键字,最后修改父结点中兄弟结点的关键字(因为兄弟结点的关键字范围改变了);如果兄弟也满了,则在原结点与兄弟结点之间增加新结点,并各复制1/3的数据到新结点,最后在父结点增加新结点的指针;

       所以,B*树分配新结点的概率比B+树要低,空间使用率更高;

小结

      
B树:二叉树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点;

      
B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关键字范围的子结点;

       所有关键字在整颗树中出现,且只出现一次,非叶子结点可以命中;

      
B+树:在B-树基础上,为叶子结点增加链表指针,所有关键字都在叶子结点中出现,非叶子结点作为叶子结点的索引;B+树总是到叶子结点才命中;

      
B*树:在B+树基础上,为非叶子结点也增加链表指针,将结点的最低利用率从1/2提高到2/3;

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图