ดัชนีช่วงบล็อก (Block Range IndexหรือBRIN)เป็น เทคนิค การจัดทำดัชนีฐานข้อมูลมีจุดประสงค์เพื่อปรับปรุงประสิทธิภาพกับตาราง ขนาดใหญ่มาก ^{[ i ]}

ดัชนี BRIN ให้ประโยชน์ที่คล้ายคลึงกันกับการแบ่งพาร์ติชันแนวนอนหรือการแบ่งส่วนแต่ไม่จำเป็นต้องประกาศพาร์ติชันอย่างชัดเจน^{[ 1 ]}

BRIN เหมาะสำหรับดัชนีบนตารางขนาดใหญ่ ซึ่งค่าคีย์ดัชนีสามารถเรียงลำดับและประเมินค่าได้ง่ายด้วย^{ฟังก์ชัน} MinMax [ ^{ii ]}

BRIN ได้รับการเสนอครั้งแรกโดย Alvaro Herrera จาก2ndQuadrantในปี 2013 ในชื่อ 'ดัชนี Minmax' ^{[ 2 ]}การใช้งานในปัจจุบันนั้นเชื่อมโยงอย่างแน่นหนากับการใช้งานภายในและเทคนิคการจัดเก็บสำหรับตารางฐานข้อมูล ทำให้มีประสิทธิภาพ แต่จำกัดเฉพาะผู้จำหน่ายบางรายเท่านั้น จนถึงปัจจุบันPostgreSQLเป็นผู้จำหน่ายเพียงรายเดียวที่ประกาศผลิตภัณฑ์ที่ใช้งานได้จริงพร้อมคุณสมบัติเฉพาะนี้ใน PostgreSQL 9.5 ^{[ 3 ] [ 4 ]}ผู้จำหน่ายรายอื่น ๆ ได้อธิบายคุณสมบัติที่คล้ายกันบางอย่าง^{[ 2 ] รวมถึง Oracle [ 5 ] [ 6 ] Netezza '} zone maps ' ^{[ 7 ] Infobright '} data packs ^{' [ 8} ] MonetDB ^{[ 9 ]}และ^{Apache Hive พร้อม} ORC / Parquet ^{[ 10 ]}

BRIN ทำงานโดยการ "สรุป" บล็อกข้อมูลขนาดใหญ่ให้เป็นรูปแบบที่กระชับ ซึ่งสามารถทดสอบได้อย่างมีประสิทธิภาพเพื่อยกเว้นบล็อกข้อมูลจำนวนมากออกจากการสืบค้นฐานข้อมูลตั้งแต่เนิ่นๆ การทดสอบเหล่านี้จะยกเว้นบล็อกข้อมูลขนาดใหญ่สำหรับการเปรียบเทียบแต่ละครั้ง ด้วยการลดปริมาณข้อมูลตั้งแต่เนิ่นๆ ทั้งโดยการแสดงบล็อกขนาดใหญ่เป็นทูเปิลขนาดเล็ก และโดยการกำจัดบล็อกจำนวนมาก BRIN จึงลดปริมาณข้อมูลรายละเอียดที่ต้องตรวจสอบโดยโหนดฐานข้อมูลแบบทีละแถวได้อย่างมาก^{[ 11 ]}

การจัดเก็บข้อมูลในฐานข้อมูลขนาดใหญ่จะถูกแบ่งเป็นชั้นและแบ่งเป็นส่วนๆ โดยที่การจัดเก็บตารางจะถูกจัดเรียงเป็น 'บล็อก' แต่ละบล็อกอาจมีขนาดประมาณ 1MB ในแต่ละส่วน^{[ iii ] [ 13 ]}และจะถูกเรียกใช้โดยการร้องขอบล็อกเฉพาะจากชั้นจัดเก็บข้อมูลบนดิสก์ BRIN เป็นชั้นสรุปข้อมูลในหน่วยความจำที่มีน้ำหนักเบาอยู่เหนือชั้นนี้ โดยแต่ละทูเปิลในดัชนีจะสรุปข้อมูลหนึ่งบล็อกเกี่ยวกับช่วงของข้อมูลที่อยู่ในนั้น ได้แก่ ค่าต่ำสุดและค่าสูงสุด และหากบล็อกนั้นมีข้อมูลที่ไม่เป็นค่าว่างสำหรับคอลัมน์ที่สนใจ^{[ 14 ]}

แตกต่างจากดัชนีแบบดั้งเดิมซึ่งระบุตำแหน่งของภูมิภาคในตารางที่มีค่าที่น่าสนใจ BRIN ทำหน้าที่เป็น "ดัชนีเชิงลบ" ^{[ 5 ]}โดยแสดงบล็อกที่ไม่น่าสนใจอย่างแน่นอนและไม่จำเป็นต้องประมวลผลต่อไป

เกณฑ์มาตรฐานง่ายๆ บางอย่างชี้ให้เห็นถึงการปรับปรุงประสิทธิภาพการค้นหาถึงห้าเท่าเมื่อใช้การสแกนดัชนี เมื่อเทียบกับตารางที่ไม่มีดัชนี^{[ 3 ]}เมื่อเทียบกับ B-tree แล้ว ดัชนีเหล่านี้ช่วยหลีกเลี่ยงค่าใช้จ่ายในการบำรุงรักษา^{[ 2 ]}

เนื่องจาก BRIN มีน้ำหนักเบามาก จึงสามารถเก็บไว้ในหน่วยความจำได้ทั้งหมด จึงช่วยหลีกเลี่ยงภาระของดิสก์ระหว่างการสแกน ซึ่งอาจไม่เป็นเช่นนั้นสำหรับ B-tree: B-tree ต้องการโหนดต้นไม้สำหรับทุกๆ ประมาณN แถวในตาราง โดยที่ N คือความจุของโหนดเดียว ดังนั้นขนาดของดัชนีจึงมีขนาดใหญ่ เนื่องจาก BRIN ต้องการเพียงทูเปิลสำหรับแต่ละบล็อก (ของหลายแถว) ดัชนีจึงมีขนาดเล็กพอที่จะสร้างความแตกต่างระหว่างดิสก์และหน่วยความจำ สำหรับตารางที่ 'แคบ' ^{[ iv ]}ปริมาตรของดัชนี B-tree จะใกล้เคียงกับปริมาตรของตารางเอง BRIN อาจมีเพียง 5–15% ของตารางเท่านั้น^{[ 15 ]}

โดยทั่วไปแล้ว ดัชนีฐานข้อมูลขนาดใหญ่จะใช้ อัลกอริธึม B-tree BRIN ไม่ได้เป็นตัวทดแทน B-tree เสมอไป แต่เป็นการปรับปรุงการสแกนดัชนีตามลำดับ โดยมีข้อดีเฉพาะ (และอาจมีขนาดใหญ่) เมื่อดัชนีตรงตามเงื่อนไขเฉพาะสำหรับการเรียงลำดับและเป้าหมายการค้นหาเป็นชุดค่าที่แคบ ในกรณีทั่วไปที่มีข้อมูลแบบสุ่ม B-tree อาจยังคงเหนือกว่า^{[ 3 ]}

A particular advantage of the BRIN technique, shared with Oracle Exadata's Smart Scanning,^[6] is in the use of this type of index with Big Data or data warehousing applications, where it is known that almost all of the table is irrelevant to the range of interest. BRIN allows the table to be queried in such cases by only retrieving blocks that may contain data of interest and excluding those which are clearly outside the range, or contain no data for this column.

A regular problem with the processing of large tables is that retrieval requires the use of an index, but maintaining this index slows down the addition of new records. Typical practices have been to group additions together and add them as a single bulk transaction, or to drop the index, add the batch of new records and then recreate the index. Both of these are disruptive to simultaneous read / write operations and may not be possible in some continuously operating businesses.^[16]

With BRIN, the slowdown from maintaining the index is much reduced compared to B-tree.^[17] Wong reports that B-tree slowed down additions to an unindexed 10GB table by 85%, but a comparable BRIN only had an overhead of 11%.^[1]

BRIN may be created for extremely large data where B-tree would require horizontal partitioning.^[14]

Creating the BRIN is also much faster than for a B-tree, by 80%.^[1] This would be a useful improvement to refactoring existing database applications that use the drop-add-reindex approach, without requiring code changes.

Multiple BRIN may be defined for different columns on a single table. However, there are restrictions.

BRIN are only efficient if the ordering of the key values follows the organisation of blocks in the storage layer.^[13][15] In the simplest case, this could require the physical ordering of the table, which is often the creation order of the rows within it, to match the key's order. Where this key is a creation date, that may be a trivial requirement.^{[14]: 9}

If the data is truly random, or if there is much churn of the key values in a 'hot' database, the assumptions underlying BRIN may break down. All blocks contain entries "of interest" and so few may be excluded early on by the BRIN range filter.

ในกรณีส่วนใหญ่ BRIN จะถูกจำกัดไว้ที่ดัชนีเดียวต่อตาราง อาจมีการกำหนด BRIN หลายรายการ แต่จะมีเพียงรายการเดียวเท่านั้นที่มีลำดับการเรียงลำดับที่เหมาะสม หากดัชนีสองรายการ (หรือมากกว่า) มีพฤติกรรมการเรียงลำดับที่คล้ายคลึงกัน อาจเป็นไปได้และมีประโยชน์ที่จะกำหนด BRIN หลายรายการในตารางเดียวกัน ตัวอย่างที่เห็นได้ชัดคือกรณีที่ทั้งวันที่สร้างและคอลัมน์ record_id เพิ่มขึ้นอย่างต่อเนื่องตามลำดับการสร้างเรคอร์ด ในกรณีอื่นๆ ค่าคีย์อาจไม่เพิ่มขึ้นอย่างต่อเนื่อง แต่ตราบใดที่ยังมีการจัดกลุ่มที่แข็งแกร่งภายในลำดับทางกายภาพของเรคอร์ด BRIN ก็จะมีประสิทธิภาพ

BRIN มีความคล้ายคลึงกับ" ดัชนีจัดเก็บข้อมูล " ของ Oracle Exadata อยู่บ้าง ^{[ 2 ] [ 5 ] [ 18 ]} Exadata มีแนวคิดที่แข็งแกร่งของ 'เลเยอร์จัดเก็บข้อมูล' ในสแต็กสถาปัตยกรรม ข้อมูลตารางจะถูกเก็บไว้ในบล็อกหรือ 'เซลล์จัดเก็บข้อมูล' บนเซิร์ฟเวอร์จัดเก็บข้อมูล เซลล์จัดเก็บข้อมูลเหล่านี้ไม่โปร่งใสสำหรับเซิร์ฟเวอร์จัดเก็บข้อมูลและจะถูกส่งกลับไปยังเอ็นจินฐานข้อมูลเมื่อมีการร้องขอ โดยใช้ตัวระบุ ก่อนหน้านี้ โหนดฐานข้อมูลต้องร้องขอเซลล์จัดเก็บข้อมูลทั้งหมดเพื่อสแกน^{[ 6 ]}

ดัชนีการจัดเก็บข้อมูลช่วยให้สามารถตัดแต่งข้อมูลในเลเยอร์นี้ได้ โดยระบุส่วนที่ไม่น่าสนใจอีกต่อไปอย่างมีประสิทธิภาพ^{[ 13 ] [ v ] [ 19 ]}ดัชนีการจัดเก็บข้อมูลจะถูกโหลดลงในหน่วยความจำบนเซิร์ฟเวอร์จัดเก็บข้อมูล เพื่อให้เมื่อมีการร้องขอเซลล์ จะสามารถกำหนดเงื่อนไขด้วยค่าการค้นหาได้ ค่าเหล่านี้จะถูกเปรียบเทียบกับดัชนีการจัดเก็บข้อมูล จากนั้นเฉพาะเซลล์ที่เกี่ยวข้องเท่านั้นที่จะต้องส่งคืนไปยังโหนดฐานข้อมูล

ข้อได้เปรียบด้านประสิทธิภาพของดัชนีจัดเก็บข้อมูลจะเห็นได้ชัดเจนที่สุดเมื่อคอลัมน์ที่มีดัชนีมีค่าว่าง จำนวนมาก ข้อได้เปรียบด้านประสิทธิภาพมหาศาลจะได้รับเมื่อทำการสแกนข้อมูลที่กระจัดกระจาย^{[ 20 ]}

การพัฒนาสำหรับ PostgreSQL ดำเนินการเป็นส่วนหนึ่งของโครงการ AXLE (Advanced Analytics for Extremely Large European Databases) ^{[ 21 ]} งานนี้ได้รับการสนับสนุนบางส่วนจาก โครงการกรอบงานที่เจ็ดของสหภาพยุโรป(FP7/2007-2013) ^{[ 22 ]}

การนำไปใช้สำหรับ PostgreSQL ปรากฏให้เห็นครั้งแรกในปี 2013 ^{[ 2 ]} BRIN ปรากฏใน PostgreSQLเวอร์ชัน 9.5 ในช่วงต้นปี 2016 ^{[ 15 ] [ 23 ]}

• การแบ่งส่วน