TsDB2/DB/core/index/chain_util.go

package index

import (
	"TsDB2/DB/core/page"
	"unsafe"
)

// insertEntrySorted 在索引页中有序插入一个条目
func insertEntrySorted(buf []byte, hdr *page.IndexHead, entry []byte) {
	entryLen := int(hdr.EntryLen)
	count := int(hdr.Count)
	entries := buf[page.IndexHeadSize : page.IndexHeadSize+count*entryLen]
	pos := count
	left, right := 0, count-1
	for left <= right {
		mid := (left + right) / 2
		midEntry := entries[mid*entryLen : (mid+1)*entryLen]
		cmp := compareEntryKeys(midEntry, entry, entryLen-4)
		if cmp >= 0 {
			pos = mid
			right = mid - 1
		} else {
			left = mid + 1
		}
	}
	allEntries := buf[page.IndexHeadSize : page.IndexHeadSize+(count+1)*entryLen]
	copy(allEntries[(pos+1)*entryLen:(count+1)*entryLen], allEntries[pos*entryLen:count*entryLen])
	copy(allEntries[pos*entryLen:(pos+1)*entryLen], entry)
	hdr.Count++
	hdr.Hdr.UseSize += uint32(entryLen)
}

func compareEntryKeys(a, b []byte, keyLen int) int {
	for i := 0; i < keyLen; i++ {
		if a[i] < b[i] {
			return -1
		}
		if a[i] > b[i] {
			return 1
		}
	}
	return 0
}

// writeToNewIndexPage 创建新的索引页，写入一个条目，并链接到索引链
func writeToNewIndexPage(handle page.HandleDb, entryPage *uint32, entry []byte, lastIdxPageID uint32) error {
	newIdxPID := handle.NewPage()
	newBuf := make([]byte, page.IndexPageSize)
	newHdr := (*page.IndexHead)(unsafe.Pointer(&newBuf[0]))
	newHdr.Hdr.Type = page.IndexDataIndex
	newHdr.Hdr.PageID = newIdxPID
	newHdr.Hdr.UseSize = uint32(page.IndexHeadSize) + uint32(len(entry))
	newHdr.EntryLen = uint16(len(entry))
	newHdr.IsLeaf = 1
	newHdr.Count = 1
	copy(newBuf[page.IndexHeadSize:], entry)
	if err := handle.SavePage(newIdxPID, newBuf); err != nil {
		return err
	}
	if *entryPage == 0 {
		*entryPage = newIdxPID
	} else if lastIdxPageID != 0 {
		linkBuf := make([]byte, page.IndexPageSize)
		if err := handle.ReadPage(lastIdxPageID, linkBuf); err == nil {
			linkHdr := (*page.IndexHead)(unsafe.Pointer(&linkBuf[0]))
			linkHdr.Hdr.NextPage = newIdxPID
			if err := handle.SavePage(lastIdxPageID, linkBuf); err != nil {
				return err
			}
		}
	}
	return nil
}