SQLite中的B-Tree实现细节分析

by admin on 2019年11月12日

  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索引的大要存款和储蓄结构中Specialspace部分,包蕴根节点、左右兄弟节点等相关索引结构信息,以致早先索求了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页。第朝气蓬勃页的眼下九贰十个字节包括了叁个别开生面包车型客车首部(文件头),它是那个文件的呈报。
文本头的个数如下:
** OFFSET SIZE DESCRIPTION
** 0 16 Header string(首部字符串卡塔 尔(阿拉伯语:قطر‎: “SQLite format 3\000”
** 16 2 Page size in bytes(页的字节数卡塔 尔(英语:State of Qatar).
** 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 马克斯 embedded payload fraction(最大的放权有效载荷分片卡塔 尔(英语:State of Qatar)
** 22 1 Min embedded payload fraction(最小的放到有效载荷分片卡塔 尔(阿拉伯语:قطر‎
** 23 1 Min leaf payload fraction(最小的页有效载荷分片卡塔 尔(阿拉伯语:قطر‎
** 24 4 File change counter (文件变化计数器卡塔 尔(英语:State of Qatar)
** 28 4 Reserved for future use (保留字节卡塔尔
** 32 4 First freelist page (第一个freelist页)
** 36 4 Number of freelist pages in the file
(本文件中freelist页的个数卡塔 尔(英语:State of Qatar)
** 40 60 15 4-byte meta values passed to higher layers()
**
持有的整数都以多方面包车型客车。

每一回匡正文件时,文件变化流量计都会扩充。那一个计数器能够让此外进度知道几时文件被涂改了,他们的cache是还是不是需求清理。

最大嵌入有效载荷分片是生龙活虎页的有着可用空间,被标准B-tree(非叶数据卡塔尔表的单身的八个所能使用的总的数量。值255意味着百分百。默许情状下,豆蔻梢头格(cell)的最一大波被节制为,至罕见4格工夫填满大器晚成页。由此,暗许的最大嵌入负荷分片是64。

设若风(Ruan patrol卡塔 尔(阿拉伯语:قطر‎华正茂页的卓有成效载荷大于了最大实用载荷,那么余下的数据将要被存放到溢出页。风度翩翩旦分配了三个溢出页,有十分大可能率会有诸许多量也被退换到这么些溢出页,不过不会让格cell的大小小于最小嵌入有效载荷分片的。

最小页有效载荷分片与纤维嵌入有效载荷分片相仿,不过它是选拔于LEAFDATA
tree中的叶节点。三个LEAFDATA的最大实用载荷分片为百分之百(只怕是值255卡塔尔国,它并不是再首部钦点。

BTree的每大器晚成页被分成三局地:首部,格(cell卡塔 尔(英语:State of Qatar)指针数组,和格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个字节都会被以为是多少。那就同意了陆13人整数变编码为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卡塔 尔(英语:State of Qatar);

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中,共占用15个字节:

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的SpecialSpace的积累结构,通过SpecialSpace能够获取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个第一字卡塔 尔(英语:State of Qatar)

       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-树的探索,从根结点起首,对结点内的基本点字(有序卡塔 尔(英语:State of Qatar)连串举办二分查找,若是命中则截至,不然踏入查询关键字所属范围的幼子结点;重复,直到所对应的孙子指针为空,或早正是卡片结点;

B-树的特色:

       1.至关心尊敬要字集结布满在整颗树中;

       2.此外多少个首要字现身且只出以后一个结点中;

       3.索求有超级大概率在非叶子结点甘休;

       4.其寻找品质等价于在显要字全集内做三遍二分查找;

       5.自动档期的顺序调节;

      
由于约束了除根结点以外的非叶子结点,最少含有M/2个孙子,确定保证了结点的起码利用率,其最底搜索品质为:

图片 20

 

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

      
所以B-树的属性总是等价于二分查找(与M值毫不相关卡塔 尔(英语:State of Qatar),也就没有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.非卡片结点也正是是卡牌结点的目录(萧疏索引卡塔尔国,叶子结点约等于是存款和储蓄(关键字卡塔 尔(英语:State of Qatar)数据的数据层;

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

 

B*树

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

图片 22

 

B*树定义了非叶子结点关键字个数最少为(2/3)*M,即块的最低使用率为2/3(替代B+树的四分之一卡塔尔国;

      
B+树的解体:当多少个结点满时,分配二个新的结点,并将原结点中一半的数量复制到新结点,最终在父结点中追加新结点的指针;B+树的和衷共济只影响原结点和父结点,而不会影响兄弟结点,所以它不要求指向兄弟的指针;

      
B*树的解体:当贰个结点满时,借使它的下四个小伙子结点未满,那么将豆蔻梢头部分数量移到兄弟结点中,再在原结点插加入关贸总协定组织键字,末了校正父结点中兄弟结点的显要字(因为兄弟结点的主要字范围改变了卡塔 尔(阿拉伯语:قطر‎;借使兄弟也满了,则在原结点与手足结点之间扩展新结点,并各复制三分之二的数额到新结点,最终在父结点扩展新结点的指针;

       所以,B*树分配新结点的票房价值比B+树要低,空间使用率越来越高;

小结

      
B树:二叉树,每一种结点只存款和储蓄一个首要字,等于则命中,小于走左结点,大于走右结点;

      
B-树:多路寻找树,种种结点存款和储蓄M/2到M个关键字,非叶子结点存款和储蓄指向首要字范围的子结点;

       全数首要字在整颗树中冒出,且只现出三遍,非叶子结点能够命中;

      
B+树:在B-树根基上,为叶子结点扩充链表指针,全部入眼字都在叶子结点中现身,非叶子结点作为叶子结点的目录;B+树总是到叶子结点才命中;

      
B*树:在B+树根底上,为非叶子结点也加进链表指针,将结点的最低利用率从四分之一拉长到2/3;

 

发表评论

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

网站地图xml地图